BJ2579 계단 오르기

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

사용한 알고리즘 : DP
난이도 : 실버 3

문제

계단을 1개 밟을때 마다 계단에 적힌 숫자만큼 점수를 얻는다.
계단은 1칸 또는 2칸을 갈 수 있으며, 1칸은 연속해서 갈 수 없다.
마지막 계단은 꼭 밟아야한다.

이때 얻을 수 있는 최고 점수를 구하시오.

문제 접근 방법

DP 알고리즘으로 문제를 해결하기 위해서는 다음의 2 조건을 만족해야한다.
1. 큰 문제를 같은 구조의 작은 문제로 분해할 수 있다.
2. 작은 문제의 최적의 해를 이용해서 큰 문제의 최적의 해를 구할 수 있다.

위의 두 경우를 만족하면 문제를 점화식의 형태로 만들어 풀 수 있다.

점화식

1. 2칸 건너서 N번 계단을 밟는 경우
   • 1칸 건너서 N-2번 계단을 밟는 경우 -- (0)
   • 2칸 건너서 N-2번 계단을 밟는 경우 -- (1)
   • (0)과 (1) 둘중에서 더 큰 점수에 N번 계단의 점수를 더한 값
2. 1칸 건너서 N번 계단을 밟는 경우
   • 2칸 건너서 N-1 계단을 밟는 경우 -- (2)
   • (2)번 점수에 N번 계단의 점수를 더한 값

코드

package Java.Y22.M03.D04;

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

public class BJ2579_StepUp {

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] step = new int[N + 1];
		int[][] dp = new int[N + 1][2];
		for(int i = 1; i < N + 1; i++) {
			step[i] = Integer.parseInt(br.readLine());
		}
		
		int[][] next = new int[2][];
		next[0] = new int[]{0,1};
		next[1] = new int[]{0};
		
		int[] gap = {2, 1};
		
		dp[1][1] = step[1];
		
		if(N == 1) {
			System.out.println(step[1]);
			return;
		}
		
		dp[2][1] = dp[1][1] + step[2];
		dp[2][0] = step[2];
		
		for(int i = 1; i < N; i++) {
			for(int j = 0; j < 2; j++) {
				for(int nj : next[j]) {
					if(i + gap[nj] > N) continue;
					
					if(dp[i + gap[nj]][nj] < dp[i][j] + step[i + gap[nj]]) {
						dp[i + gap[nj]][nj] = dp[i][j] + step[i + gap[nj]];
					}
				}
			}
		}
		
		System.out.println(Integer.max(dp[N][0], dp[N][1]));
		
	}

}