[백준/JAVA] 2579 - 계단 오르기

문제 정보

https://www.acmicpc.net/problem/2579

 

문제 

 

문제 해결 과정

완전 탐색 풀이

매 번 계단을 한 칸(+1칸)  또는 두 칸(+2칸)을 오르는 경우, 가능한 경우의 수는 다음과 같다.

 이동 1(+1칸/+2칸) x 이동 2(+1칸/+2칸) x ... x 이동 k(+1칸/+2칸) = 2^k가지

 

이때 계단의 개수가 최대 300개이므로, 이동은 최소 150번(+2칸으로만) 최대 300번(+1칸으로만) 일어나게 된다.

따라서, 150 ≤ k ≤ 300이므로, 2^150 < 시간복잡도 < 2^300일 것이고 문제 시간 제한인 1초를 초과하게 된다.

 

DP 풀이

계단 4에 도착할 수 있는 경우를 주목해보았을 때, 다음과 같이 나뉘어 질 수 있다.

• 계단 3에서 + 1칸
• 계단 2에서 + 2칸

연속하여 세 개의 계단을 밟을 수 없으므로, 불가능한 경우를 삭제(위에서 빨간색 x)해 보았다. 삭제된 것들을 보면, 규칙을 찾을 수 있었다. 

+1칸을 이동하여 현재 계단에 도착한 경우, 이전에도 +1칸해서 이동한 경우는 불가능
(+2 +1 +1도 불가능하고, +1 +1 +1도 불가능하다) 

따라서, +1칸을 이동하여 현재 계단에 도착한 경우는, 이전에 무조건 +2칸해서 이동한 경우만 가능함

 

 

즉, 현재 계단의 번호와 이전에 +1칸을 연속으로 몇 번 이동했는지가 중요한 요소가 된다. 따라서 dp 배열을 2차원으로 다음과 같이 정의하였다.

dp[i][j] : 현재 i번 계단에 도착한 경우, +1칸을 연속하여 j번 이동했을 때의 총점의 최댓값

+2칸 이동 : dp[i][0] = Max(dp[i-2][0], dp[i-2][1], dp[i-2][2]) + i번 계단의 점수
+1칸 이동 : dp[i][1] = dp[i-1][0] + i번 계단의 점수

 

DP 풀이의 시간복잡도

위의 2차원 배열을 1번 계단부터 N번 계단까지 차례대로 채워나가는 시간이므로, 대략 N(계단수) * 2 = 300 * 2 = 600이므로 제한 시간내에 충분히 풀 수 있다.

 

코드

class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine()); // 계단의 수
		int[][] dp = new int[n+1][3]; // dp[i][j] : i번째 계단일 때, +1이 연속하여 j번 나왔을때의 총점 최댓값
		
		dp[1][1] = Integer.parseInt(br.readLine()); // +1칸
		
		if(n >= 2) {
			int n2 = Integer.parseInt(br.readLine());
			dp[2][0] = n2; // +2칸
			dp[2][2] = dp[1][1] + n2; // +1칸 +1칸			
		}
		
		for(int i=3; i<=n; i++) {
			int num = Integer.parseInt(br.readLine()); // 현재 적힌 계단의 수
			
			// +1칸하여 계단 밟은 경우
			dp[i][1] = dp[i-1][0] + num; // 그 이전에 +1칸하여 계단 밟으면 안됨 (+1,+1,+1 or +2,+1,+1 모두 불가)
			
			// +2칸하여 계단 밟은 경우
			dp[i][0] = Math.max(Math.max(dp[i-2][0], dp[i-2][1]), dp[i-2][2]) + num;
		}
		
		System.out.println(Math.max(Math.max(dp[n][0], dp[n][1]), dp[n][2])); // 마지막 계단은 반드시 밟아야 함
	}
}