[백준] 21317번: 징검다리 건너기 - java

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

public class Main {
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int[][] rock = new int[n][2];
		int[] dp = new int[n + 1];
		for (int i = 1; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			rock[i][0] = Integer.parseInt(st.nextToken()); // 작은 점프
			rock[i][1] = Integer.parseInt(st.nextToken()); // 큰 점프
		}
		int k = Integer.parseInt(br.readLine());

		if (n >= 2) {
			dp[2] = rock[1][0];
		}
		if (n >= 3) {
			dp[3] = Math.min(rock[1][1], dp[2] + rock[2][0]);
		}

		int energy = Integer.MAX_VALUE;
		if (n >= 4) {
			for (int i = 4; i <= n; i++) { // 매우 큰 점프를 할 수 있는 위치
				for (int j = 4; j <= n; j++) {
					if (i == j) { // 큰 점프를 할 수 있는 돌의 위치
						dp[j] = dp[j - 3] + k;
					} else
						dp[j] = Integer.MAX_VALUE;
					dp[j] = Math.min(dp[j], Math.min(dp[j - 2] + rock[j - 2][1], dp[j - 1] + rock[j - 1][0]));
				}
				energy = Math.min(energy, dp[n]);
			}
		} else {
			energy = dp[n];
		}
		System.out.println(energy);
	}

}

 

매우 큰 점프를 전체에서 1번 사용할 수 없다는 조건을 제외하면 아주 쉽게 풀리는 문제이다.

dp[i] 를 dp[i] 돌까지 도달하는데 걸린 최소 에너지라고 하자.

매우 큰 점프를 제외한 dp점화식은 다음과 같다.

rock[i][0] => i번째 돌에서 작은 점프를 하기 위해 필요한 에너지 
rock[i][1] => i번째 돌에서 큰 점프를 하기 위해 필요한 에너지
dp[i] = Math.min(dp[i-2] + rock[i-2][1], dp[i-1] + rock[i-1][0]);

 

그러나 여기서 매우 큰 점프를 추가한다면? 

매우 큰 점프를 1번밖에 하지 못한다는 조건이 까다롭게 느껴졌다.

n<=20 이라 크지 않은 숫자이기 때문에,

큰 점프를 하여 도착하는 돌의 위치를 for문을 통해 지정하였고, 모든 케이스를 확인하였다.  (i=4~n)

* 큰 점프을 하여 도달할 수 있는 돌은 4번째 돌부터 시작한다.

 

 

for (int i = 4; i <= n; i++) { // 매우 큰 점프를 할 수 있는 위치
		for (int j = 4; j <= n; j++) { // dp[j] 구하기
			if (i == j) { // 큰 점프를 할 수 있는 돌의 위치
				dp[j] = dp[j - 3] + k;
			} else
				dp[j] = Integer.MAX_VALUE;
			dp[j] = Math.min(dp[j], Math.min(dp[j - 2] + rock[j - 2][1], dp[j - 1] + rock[j - 1][0]));
		}
		energy = Math.min(energy, dp[n]);
}

만약 아주 큰 점프를 하여 j번째 돌에 도착하였다면? (i==j)

=> dp[j] = dp[j-3] + k 가 될 것이다.

따라서 작은 점프, 큰 점프, 아주 큰 점프를 하였을 때의 dp[j] 값을 비교하여 dp[j] 를 갱신해준다.

Math.min(dp[j-3]+k, Math.min(dp[j - 2] + rock[j - 2][1], dp[j - 1] + rock[j - 1][0]));