백준 22869 (징검다리 건너기 (small))

문제

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

N개에 돌에 부여된 수 A1, A2, A3, ... An 이 있다.

여기서 맨 왼쪽 돌부터 오른쪽 방향으로만 이동하여 An에 도달할 수 있는지 구하는 문제이다.

문제의 조건은 다음과 같다.

1. 돌을 한번 건너갈 때마다 쓸 수 있는 힘은 최대 K이다.
2.  i번째 돌에서 j(i < j)번째 돌로 이동할 때 (j - i) × (1 + |Ai - Aj|) 만큼 힘을 쓴다.

---

내가 처음에 접근한 방법은 다음과 같다.

dp[i][j] = 1이면 i에서 j로 이동 가능, 0이면 이동 불가능

for(int i=1;i<n;i++){
        for(int j = i+1;j<=n;j++){
            if(((j-i) * (1 + Math.abs(arr[i]-arr[j]))) <= k){
                dp[i][j]=1;
            }
            else dp[i][j]=0;
        }
}

따라서 이를 바탕으로 N 부터 시작해서 1까지 도달 할 수 있느냐를 체그 했다.

sol(n)

private static void sol(int start){
        if(start == 1){
            chk = true;
            return;
        }
        for(int i=1;i<start;i++){
            if(dp[i][start]==1){
                sol(i);
            }
            if(chk)return;
        }
    }

하지만 25%에서 시간초과가 발생했다.

 

다른 방법으로 접근해보았다.

바로 dfs와 메모이제이션을 사용하는 방법이다.

1번 돌이 2, 3, 4번 돌로 갈 수 있다.

2번 돌이 3, 4, 5번 돌로 갈 수 있다면, 1번 돌이 3, 4번을 이미 방문했으므로 2번돌은 5번돌만 방문하면 된다.

dp[i] = true 이면 i번째 돌은 방문 했다는 의미이다.

dfs(1);

private static void dfs(int start){
        if(start == n){
            dp[n] = true;
            return;
        }

        if(dp[start])return;

        dp[start] = true;

        for(int i = start+1;i<=n;i++){
            if((i-start)*(1+Math.abs(arr[start]-arr[i]))<= k){
                dfs(i);
            }
        }
    }

---

전체 코드이다.

public class Main {
    private static boolean[] dp;
    private static int[]arr;
    private static int n;
    private static int k;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        dp = new boolean[n+1];
        arr = new int[n + 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++)
            arr[i] = Integer.parseInt(st.nextToken());

        dfs(1);

        if (dp[n]) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }

    }
    private static void dfs(int start){
        if(start == n){
            dp[n] = true;
            return;
        }

        if(dp[start])return;

        dp[start] = true;

        for(int i = start+1;i<=n;i++){
            if((i-start)*(1+Math.abs(arr[start]-arr[i]))<= k){
                dfs(i);
            }
        }
    }

}