BOJ 2579 계단 오르기

 

2579번: 계단 오르기

다이나믹 프로그래밍으로 풀어주는 문제이다.

일단 조건을 살펴보자

 

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

즉 지금 i번째 계단에 와있다고 생각했을때 세가지의 경우가 있다.

 

1. 현재 계단을 밟는다. + 직전 바로 옆 계단을 밟았다.

2. 현재 계단을 밟지 않는다 

3. 현재 계단을 밟는다 + 직전 바로 옆 계단을 밟지 않았다.

 

그리고 마지막 계단은 꼭 밟아주는 것이 조건이기 때문에, 마지막 값은 따로 빼주도록 한다.

그렇게 되면 총 계단의 수가 n개라고 할 때, n-1번째 계단에서 1번의 선택을 하게되면 마지막 계단을 포함해 3개의 계단을 연속으로 밟게된다. 따라서 첫번째 경우는 해답에서 제외된다.

그러면 나머지 두 해답중에 더 큰 값을 찾으면 되겠다.

 

위의 세가지의 경우를 그대로 점화식으로 옮겨보면

1. dp[i][1] = step[i] + dp[i-1][3] //직전계단을 밟았고, 세 계단을 연속으로 밟으면 안되므로 dp[i-1][3]을 더해준다.

2. dp[i][2] = max(dp[i-1][1], dp[i-1][3])  // 현재 계단을 밟지 않으므로 이전 두값중에서 더 큰값을 가지고 온다.

 // 여기서 dp[i-1][2] 가 제외되는 이유는, 당연하다. 계단을 두개 이상 밟지 않으면 안되기 때문이다.

3. dp[i][3] = step[i] + dp[i-1][2]  //직전 계단을 밟지 않았으므로.

 

그리고 마지막에는 dp[n-1][2] 와 dp[n-1][3] 중 더 큰 값에다가 step[n] 을 더해주면 된다.

 

이 문제는 포도주 시식문제와 로직이 매우매우매우 비슷하다. 

처음에는 마지막 계단을 무조건 포함시켜야한다는 조건때문에 뒤에서부터 dp table을 채워올까 생각했으나, 포도주 시식처럼 '현재 i번째 선택' 에 대하여 보니, 세 가지의 경우가 나왔다.

 

 

아래는 자바 소스이다.

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

public class Main {
	
	private static int max(int n,int m) {
		if(n>m) return n;
		else return m;
	}
	private static int[] step;
	private static int[][] dp;
	public static void main(String[] args)throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk= new StringTokenizer(br.readLine());
		int n = Integer.parseInt(stk.nextToken()); // 계단 수 
		
		step = new int[n+1];
		dp = new int[n+1][3];
		for(int i =1; i<n+1; i++) {
			stk = new StringTokenizer(br.readLine()); 
			int input= Integer.parseInt(stk.nextToken());
			step[i]=input; //저장 
		}
		for(int i= 1;i < n ; i++) {
			dp[i][0]=step[i]+dp[i-1][2]; //경우 1번. 현재 계단 밟음 + 이전 계단 밟음 
			dp[i][1]=max(dp[i-1][0],dp[i-1][2]); //경우 2번. 현재 계단 안밟음
			dp[i][2]= step[i]+dp[i-1][1]; //경우 3번 . 현재 계단 밟음 + 이전 계단 안밟음
		}
		int res = max(dp[n-1][1],dp[n-1][2]);
		res+=step[n];
		System.out.println(res);
	}
}