EunSung.log

계단오르기

3 min read

문제 정보

풀이

규칙에 의하면 3개의 계단을 연속해서 밟으면 안되고, 마지막 도착 계단은 반드시 밟아야 한다.

즉, 마지막 도착 계단 이전 계단을 밟는 경우와, 밟지 않는 경우로 나뉘어 진다. (도착 계단을 n이라고 했을 때, n-3 -> n-1 -> n과 n-2 -> n의 두 경우)

  1. n-1번째 계단을 밟는 경우 (n-3 -> n-1 -> n) - 3개의 계단을 연속해서 밟을 수 없으므로, n-1번째 계단을 밟는다면 n-2번째 계단은 반드시 건너뛰어야 한다. - 따라서 n-3번째 계단에서 n-1번째 계단을 밟고 n번째 계단으로 오는 경우다. - → dp[i - 3] + stair[i - 1] + stair[i]
  2. n-1번째 계단을 밟지 않는 경우 (n-2 -> n)
    • n-2번째 계단까지의 최대 점수에 n번째 계단의 점수를 더하면 된다.
    • → dp[i - 2] + stair[i]

두 경우 중 최대값이 dp[i]이므로 점화식은 다음과 같다.

  • dp[i] = stair[i] + max(dp[i-3] + stair[i - 1], dp[i - 2])

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public 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[] stair = new int[n + 1];
        for (int i = 1; i <= n; i++)
            stair[i] = Integer.parseInt(br.readLine());
        
        if (n == 1) {
            System.out.println(stair[1]);
            return;
        }
        if (n == 2) {
            System.out.println(stair[1] + stair[2]);
            return;
        }
        
        int[] dp = new int[n + 1];
        dp[1] = stair[1];
        dp[2] = stair[1] + stair[2];
        dp[3] = Math.max(stair[1], stair[2]) + stair[3];
        
        for (int i = 4; i <= n; i++)
            dp[i] = Math.max(dp[i - 3] + stair[i - 1], dp[i - 2]) + stair[i];
        
        System.out.println(dp[n]);
        
    }
}

dp[3]은 점화식을 적용하면 max(dp[1], dp[0] + stair[2]) + stair[3]인데, dp[0] = 0으로 초기화되므로 점화식을 그대로 적용할 수 있어 별도로 처리를 안해도 된다.

다만 코드에서는 dp[0]을 명시적으로 초기화하지 않아 dp[3]을 따로 처리했다.

백링크