동적 계획법 예제(3). 백준 [2579] 계단 오르기

백준 [2579] 계단 오르기

동적 계획법을 이용하는 문제이다. 이 문제에는 총 세 가지의 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

얼핏 보면, 움직일 수 있는 두개의 계단 중 큰 수를 가진 계단을 이용하는 문제로 볼 수 있다. 하지만, 이것은 탐욕 법을 이용한 문제 풀이이며, 해답이 아니다.

동적 계획법으로 모든 경우의 수를 살펴 보아야 한다. 연속하는 세 개의 계단을 밟을 수 없고, 마지막 계단은 무조건 밟아야 하기 때문에 배열을 이용하여 i번째 계단이 마지막이라 가정하고 하나씩 풀어 나가면 해결된다.
마지막 계단이라 가정한 계단이 갖는 경우의 수는 2가지 이다. ?
마지막 계단을 i계단이라 하면,

1. i(마지막 계단) + i-1(전 계단) +i-3까지의 합(한 칸 건너뛴 계단까지의 합)
2. i(마지막 계단) + i-2까지의 합(전 전 계단까지의 합)

이 두 가지 경우 중, 더 큰 쪽을 선택하여 가지면 된다. 
다음은 JAVA로 작성한 코드이다.

import java.util.Scanner;

public class stepGame {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		//계단의 수를 저장
		int n = scan.nextInt();

		//각 계단이 가지는 값을 저장
		int step[] = new int[n];
		for( int i = 0 ; i < n ; i++ ) {
			step[i] = scan.nextInt();
		}

		//각 계단까지의 최대의 수를 저장
		int solution[] = new int[n];

		
		//기저 조건보다 작은 값들은 따로 처리
		if( n >= 3 ) {
			
			//기저 조건 설정
			solution[0] = step[0];		
			solution[1] = step[0]+step[1];
			solution[2] = Math.max(step[1]+step[2], step[0]+step[2]);
			
			//두가지 경우의 수중 큰수를 선택
			for( int i = 3 ; i < n ; i++ ) {
				solution[i] = Math.max(step[i]+solution[i-2],step[i]+step[i-1]+solution[i-3]);
			}
			System.out.println(solution[n-1]);
		}else{
			//기저 조건보다 작은 값들 처리
			for(int i = 0 ; i < n ; i++ ) {
				solution[n-1] += step[i]; 
			}
			System.out.println(solution[n-1]);
		}

	}
}