[백준,BOJ 2579] 계단 오르기(JAVA 구현)

-내 생각

  이전까지 풀어봤던 dp문제들과는 조금 차이점이 있다. 점화식을 세워야 하는데, 어떻게 세워야 할지 몰라서 다른 분들의 글을 참고했다.. 나 스스로 푸는 게 없다 무슨 ㅋㅋㅋㅋ 어찌 됐든 풀 수 없다면 풀이를 분석하고 외우는 수밖에 없을 거다....

 

-해법

  우선 점화식을 세우기 위해서는 문제에서 주어진 조건을 활용해야 하는 것 같다. 문제에서 주어진 조건은 1. 계단은 한 칸 또는 두 칸을 오를 수 있다. 2. 계단을 3개 연속 밟을 수는 없다. 3. 마지막 계단은 무조건 밟아야 한다.인데, 점화식을 세우는 방법은 계단이 존재할 때 한 개의 칸을 기준으로 가능한 경우의 수를 찾는 것이다. 계단을 밟을 수 있는 경우의 수는 아래의 표와 같다.

n-3	n-2	n-1	n번 째 칸
O	X	O	O
O 또는 X	O	X	O

  위의 표가 의미하는 바는 한 개의 칸에 도착할 수 있는 경우의 수가 두 가지가 있다는 것이다. 즉, 이전 칸에서 한 칸을 오른 경우, 이전 이전 칸에서 2칸을 오른 경우이다. 한 칸을 오른 경우는 3개의 계단을 연속해서 밟을 수 없으므로 자동적으로 N-2번째 칸은 밟지 못하므로 N-1칸에 도착할 수 있는 경우는 N-3칸에서 2칸을 이동한 경우밖에 없으므로 N-3역 시 무조건 밟아야 한다. 

 

  이전 이전 칸에서 2칸을 오른 경우는 3개의 계단을 연속해서 밟을 수 없으므로 N-1은 밟을 수 없고, N-2는 밟아야 한다. 이후 N-2에 도착하기 위한 경우는 상관이 없다. 왜냐하면 N-3을 밟든 밟지 않든 N-2에는 도착할 수 있기 때문이다. 이를 바탕으로 점화식을 세워보면 dp [n] = dp [n-1] + cost [n]이 두 번째 경우의 점화식이고 dp[n] = cost[n -1] + cost[n] + dp[n-3]이 첫 번째 경우의 점화식이다. 이 두 결과 중 최댓값을 dp 배열에 저장해주면 된다.

 

  여기까지 이해하고 나서 의문이 생겼었는데 왜 첫 번째 경우의 점화식에서는 dp[n-1] + cost[n] + dp [n-3]가 아니고  cost [n-1] + cost [n] + dp [n-3] 이냐는 것이었다. 그 이유는 N-3까지의 누적 값이 저장되어 있다고 할 때, N-1을 밟은 후 N을 밟아야 하기 때문에 N-1 + N이 사실상 비용이 되는 것이다. 만약 N-1의 누적 값을 +N 해준다면, 누적에 누적이 되므로 틀리게 되는 것이다. 이제 이 점화식을 이용해서 코딩을 하면 된다. 

 

  너무 어렵다..

import java.util.*;

public class Main {
	static int n;
	
	static int dp[], cost[];
	
	
	public static void main(String[] args)   {
		Scanner sc = new Scanner(System.in);
		
		n=sc.nextInt();
		cost = new int[n+1];
		dp = new int[n+1]; 
		
		
		for(int i=1;i<=n;i++) {
			cost[i]=sc.nextInt();
		}
		
        // N-1 ,N-2 ,N-3을 고려해야 하므로 1번과 2번 값은 미리 저장해둔다.
		dp[1] = cost[1]; 
		dp[2] = Math.max(dp[1] + cost[2], cost[2]);
		
		for(int i=3;i<=n;i++) {
			dp[i] = Math.max(dp[i-2] + cost[i] , cost[i-1] + dp[i-3] + cost[i]);
			
		}
		
		System.out.println(dp[n]);
		
	}
	
}