백준 22869[자바] java 징검다리 건너기(small)

문제 링크: https://www.acmicpc.net/problem/22869

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

▶문제

 N개의 돌이 일렬로 나열 되어 있다. N개의 돌에는 수 A1A2...Ai...AN로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다.

1. 항상 오른쪽으로만 이동가능하다.
2.  i번째 돌에서 (i < j)번째 돌로 이동할 때 (j - i) × (1 + |Ai−Aj|) 만큼 힘을 쓴다.
3. 돌을 한번 건너갈 때마다 쓸 수 있는 힘은 최대 K이다.

이때, 가장 왼쪽 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너갈 수 있는지 구해보자.

---

▶입력

첫 번째 줄에 돌의 개수 N와 쓸 수 있는 최대 힘 K가 공백으로 구분되어 주어진다.

두 번째 줄에는 N개의 돌의 수 Ai가 공백으로 구분되어 주어진다.

---

▶출력

가장 오른쪽에 있는 돌로 이동할 수 있다면 YES를 출력한다. 만약 이동하지 못하는 경우에는 NO를 출력한다.

---

▶해설

DP문제 입니다. 마지막 돌에 도달할 수 있는지 없는지 찾는 문제입니다. 조건을 살펴보겠습니다.

 

1. 최대 힘 보다 큰 힘은 낼 수 없다.

2. 다음 돌로 가는데 필요한 힘-> (앞으로 갈 돌 - 현재 돌)의 인덱스 * (1+ 절댓값(현재돌-다음에갈 돌의 힘)

 

문제를 풀려면 dfs + 메모리제이션이 필요합니다.

 

돌의 이동경로를 보겠습니다. 

 

1에서 갈 수 있는 돌이 2, 3, 4라면 2, 3, 4를 다음 들릴 곳으로 설정하고, 앞으로는 들린 곳이므로 앞으로 들릴 필요는 없습니다. 

2에서 갈 수 있는 돌이 3, 4라면 1에서 이미 3, 4 를 들렸으므로 실행할 필요없이 종료합니다.

 

위와 같은 알고리즘으로 현재 돌에서 들릴 수 있는 모든 곳을 식별한 후 다음 돌에서는 들리지 않는 형식으로 진행하면 됩니다. 

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

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

전체 코드

import java.io.*;
import java.util.*;

public class Main {
    static int n,k;
    static int []arr;
    static boolean[]dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


        String[] s1 = br.readLine().split(" ");

        n = Integer.parseInt(s1[0]);
        k = Integer.parseInt(s1[1]);

        arr = new int[n];

        String[] s = br.readLine().split(" ");

        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(s[i]);
        }

        dp = new boolean[n+1];


        dfs(1);

        System.out.println(dp[n]?"YES":"NO");
    }

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

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