[백준] BOJ 2579번 계단 오르기 (Java)

문제

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

 

풀이

DP를 활용해서 풀면 된다. 

문제에 나온 예제를 예로 들어보자.

idx	0	1	2	3	4	5
score[idx]	10	20	15	25	10	20

 

배열 d[idx] (dp)에 들어가는 값은 0부터 시작해서 idx번째 계단을 밟았을 때 얻을 수 있는 점수의 최댓값으로 정의한다.

 

문제 조건에 따라 마지막 계단은 반드시 밟아야 하는 상황이다.

따라서 d[5]의 입장에서 시작해 보자. 

5번째 계단을 밟으면 가능한 상황은 3번째 계단을 밟거나, 4번째 계단을 밟은 상황 두 가지이다.

하지만 그렇다고 d[n] = max(d[n-1], d[n-2]) + score[n] 로 점화식을 세우면 안 된다. 

문제에 명시된 "계단을 3개 연속해서 밟을 수 없다" 는 조건이 위배될 수 있기 때문이다.

 

만일 3번째 계단을 밟았다고 쳐보자.

그러면 자연스럽게 3/4/5번째 계단에 대해 'O/X/O'으로 계단을 3개 연속 밟지 않는다.

만일 4번째 계단을 밟았다고 쳐보자.

그러면 3/4/5번째 계단에 대해 '?/O/O' 상태가 된다. 3번째 계단을 밟지 않았다는 보장이 없다. 

4번째 계단 입장에서 2번째 계단을 밟는 것보다 3번째 계단을 밟는 것이 점수의 최댓값을 얻을 수 있었다면 3번째 계단의 점수를 선택할 것이기 때문.

 

따라서 4번째 계단을 밟은 경우, 3번째 계단을 반드시 밟지 않는다는 조건을 추가해주어야 한다.

이는 '4번째 계단이 반드시 2번째 계단을 밟은 경우'라고 정의할 수 있고, 식으로는 d[2] + score[4]로 나타낼 수 있다.

이를 다시 5번째 계단의 입장에서 식을 세워본다면 d[n-3] + score[n-1]로 나타낼 수 있다.

따라서 점화식은 d[n] = max(d[n-3] + score[n-1], d[n-2]) 가 된다 ! 

 

import java.util.Scanner;

public class Main {
	static int[] step;
	static int[] d;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		step = new int[n];
		d = new int[n];
		for(int i=0; i<n; i++) {
			step[i] = sc.nextInt();
		}
		d[0] = step[0];
		System.out.println(dp(n-1));
		sc.close();
	}
	
	public static int dp(int n) {
		if(n<0) return 0;
		if(d[n]!=0) return d[n];
        
		return d[n] = Math.max(dp(n-2), dp(n-3)+step[n-1])+step[n];
	}
}