백준 2579

문제

---

계단은 한 번에 한 계단 또는 두 계단 씩 오를 수 있고

연속된 세 계단을 밟아서는 안 된다고 함.

먼저 N이 0일 때는 시작 지점이라고 하자.(그래야 계산하기 편할 듯 ㅠ)

따라서 N 번째 계단을 밟았다고 가정했을 때...

1) N - 2 번째 계단을 밟고 두 계단 올라 N 번째 계단을 밟았다

2) N - 3 번째 계단을 밟고 두 계단 올라 N - 1 번째 계단 밟고 N 번째 계단 밟았다.

위의 두 가지 경우 중 하나

두 경우 중 밟은 계단의 숫자의 합이 더 큰 쪽을 골라나가면 될듯

---

Code

package test;

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

public class P2579 {
	
	private static int[] step;
	private static Integer[] dp; // dp[N] : N 번째 계단까지 밟은 계단에 적힌 수의 최대 합
	
	public static void main(String[] args) throws IOException  {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		step = new int[N + 1];
		dp = new Integer[N + 1];
		
		for(int i = 1; i <= N; i++) {
			step[i] = Integer.parseInt(br.readLine());
		}
		
        /*
        굳이 dp[0]을 초기화 해줘야하나?
        
        안그러면 재귀할 때 인덱스 오류 난다....
        
        ex) N == 3일 때 find_maxSum(3) 계산 시
     	find_maxSum(0) 계산 --> find_maxSum(-2) 계산해야 함.
        N == 0인 경우는 시작 지점이므로 step[0](==0)으로 초기화해주자.
        */
        
		dp[0] = step[0];
		dp[1] = step[1];
		if(N >= 2) {
			dp[2] = step[1] + step[2]; 
		}
		
		System.out.println(find_maxSum(N));
		
	}
    
    /*
    N 번째 계단을 밟았다고 가정했을 때...

	1) N - 2 번째 계단을 밟고 두 계단 올라 N 번째 계단을 밟았다

	2) N - 3 번째 계단을 밟고 두 계단 올라 N - 1 번째 계단 밟고 N 번째 계단 밟았다.

	위의 두 가지 경우 중 하나
    */
	private static int find_maxSum(int N) {
		if(dp[N] == null) {
			dp[N] = Math.max(find_maxSum(N - 2), find_maxSum(N - 3) + step[N - 1]) + step[N];
		}
		return dp[N];
	}
	
}

---

참고 : https://st-lab.tistory.com/132