[백준] Silver I.징검다리 건너기(small)

https://www.acmicpc.net/problem/22869

 

 

사용 알고리즘

• 다이나믹 프로그래밍

 

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/*
    테이블: d[j]: j번째 돌에 도달하는 최소 에너지
    점화식: d[j]: Math.min(d[j], d[i] + energy)
 */
public class Main2 {
    static int n, 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());
        int [] s = new int[n + 1];
        int [] d = new int[n + 1];

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

        for(int i = 1; i <= n; i++) {
            d[i] = Integer.MAX_VALUE;
        }
        d[1] = 0;

        for(int i = 1; i < n; i++) {
            for(int j = i + 1; j <= n; j++) {
                int energy = (j - i) * (1 + Math.abs(s[i] - s[j]));
                if (energy <= k && d[i] != Integer.MAX_VALUE) {
                    d[j] = Math.min(d[j], d[i] + energy);
                }
            }
        }

        if (d[n] != Integer.MAX_VALUE) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}

 

 

회고

 

처음에 energy <= k일때, d[j] = 0으로 초기화 시켜주고, i = j로 시작점을 업데이트 해줬는데 예제만 통과하고 틀렸다. 애초에 dp를 사용한 방식이 아니였다.

 

처음 상태의 d[i]

0

MAX_VALUE

MAX_VALUE

MAX_VALUE

MAX_VALUE

 

처음 돌에서 순회했을 때 이동 가능한 위치

0

MAX_VALUE

2

MAX_VALUE

MAX_VALUE

 

 

세번 째 돌에서 순회했을 때 이동 가능한 위치

0

MAX_VALUE

2

MAX_VALUE

5

 

 

마지막 d[n]이 MAX_VALUE라면 도달하지 못했다는 뜻이고, 아니라면 도달했다는 뜻이다.

 

문제를 풀면서 한가지 조건을 놓쳤는데,

if (energy <= k && d[i] != Integer.MAX_VALUE) {
    d[j] = Math.min(d[j], d[i] + energy);
}

 

d[i]가 MAX_VALUE가 아닐때만 순회를 해야한다. 당연한 소리다. 왜냐면 값이 d[i] = Integer.MAX_VALUE라면 이동할 수 없는 곳인데 다시 그쪽에서 순회를 한다는게 말이 안되기 때문이다.