백준 2579 - 계단 오르기 JAVA

문제

입출력 조건, 테스틑케이스

해당 문제를 접근했을 때 머리가 굳어있어서 그런지 점화식을 찾고도 구현을 하지 못했다. 그래도 이 문제 덕에 DP에 좀 더 익숙해진 것 같다.

문제 접근 과정
1. 계단 갯수는 최대 300개, 점수는 10,000 이하 : 최대 3,000,000(연속으로 계단 올라간다는 조건 무시) -> int 선언
2. 한 번에 +1 or +2씩 계단 오를 수 있지만 연속된 세 계단 금지
3. 도착 계단은 반드시 밟기
4. 그렇다면 이미 목적 계단 가기 이전의 특정 계단을 밟는 순간 최댓값을 알 수 있지 않을까?
5. n번 째 계단까지의 max 합 = n번 째 계단의 점수 + max( (n-2번째까지의 max 합), (n-3번째 까지의 max + n-1번째 계단의 점수)) 
6. 2번에서 연속된 세 계단을 오를 수 없다고 했기 때문에 강제로 이전 계단(n-1)을 밟았을 경우에는 무조건 n-3을 밟는 다는 전제로 점화식 세웠음.
7. 점화식을 다 찾고도 아무 생각 없이 백트래킹으로 코딩을 하고 있는 나 자신을 발견...

소스코드는 탑 다운 방식(재귀)으로 작성하였습니다.

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

public class Boj_2579 {	
	static int answer = 0;
	static int stairCount;
	static int stairScore[];
	static int dp[];
	public static void main(String[] args) throws NumberFormatException, IOException {
		// 계단별 점수 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		stairCount = Integer.parseInt(br.readLine());
		dp = new int[stairCount+1];
		Arrays.fill(dp, -1);
		stairScore = new int[stairCount+1]; // 0번째 안 씀
		for (int i = 1; i <= stairCount; i++) {
			stairScore[i] = Integer.parseInt(br.readLine());
		}
		
		// 계단 올라가기 시작
		answer = start(stairCount);
		System.out.println(answer);
	}

	private static int start(int n) {
		// 계단 갯수 300, 점수는 10,000이하 -> 최대 3,000,000 -> int선언
		// 한 번에 +1 or +2
		// 연속된 세 계단 금지 -> +1 && +1 금지
		// 도착 계단 반드시 밟기
		// 이미 특정 계단 밟는 순간 최댓값을 알 수 있음
		// n번 째 계단까지의 합 = n+  max((n-2번째까지의 합max) or (n-3번째까지의 합max +n-1))
		if(n <= 0)return 0;
		
		if(dp[n] == -1) return dp[n] = stairScore[n] + Math.max(start(n-2), start(n-3) + stairScore[n-1]);
		
		return dp[n];
	}
	
}