[BOJ_22869] 징검다리 건너기 (small)

설명

---

저는 DP 형태의 메모리제이션을 활용하여서 문제를 풀었습니다. 보시다 싶이 문제 조건만 맞추면 풀 수 있는 문제라서 따로 풀이가 필요하지는 않을 듯하고 메모리제이션을 적절히 사용하는 것이 포인트 일 것 같습니다.

 

 

코드

---

package BOJ.Dynamic_Programming;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_22869 {
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine());

        int N = Integer.parseInt(tk.nextToken());
        int K = Integer.parseInt(tk.nextToken());

        tk = new StringTokenizer(in.readLine());

        int[] A = new int[N];
        int[] dp = new int[N];
        for (int i = 0; i < N; i++){
            A[i] = Integer.parseInt(tk.nextToken());
        }
        dp[0] = 1;
        for (int i = 0; i < N - 1; i++){
            if(dp[i] == 1) {
                for (int j = i + 1; j < N; j++) {
                    if (((j - i) * (1 + Math.abs(A[i] - A[j]))) <= K) {
                        dp[j] = 1;
                    }
                }
            }
        }
        if(dp[N - 1] == 0)
        {
            System.out.println("NO");
        }
        else {
            System.out.println("YES");
        }
    }
}

 

22869번: 징검다리 건너기 (small)