BOJ02579 계단 오르기

https://www.acmicpc.net/problem/2579 (opens new window)

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

제출 코드

계단은 연속으로 세 개를 밟을 수 없기 때문에 세 개를 연속으로 밟을 때를 제외하고 가장 큰 값을 dp 테이블에 저장한다.

아래는 현재 계단를 밟지 않는 경우와 전전 의자 + 현재 계단을 밟은 경우를 비교한 것이다.

dp[i] = Math.max(dp[i - 3] + stairs[i - 1], dp[i - 2]) + stairs[i];

아래는 최종 제출 코드이다.

import java.util.Scanner;

public class BOJ2579 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[] stairs = new int[n];
        int[] dp = new int[n];

        for (int i = 0; i < stairs.length; i++) {
            stairs[i] = scanner.nextInt();
        }

        for (int i = 0; i < stairs.length; i++) {
            if (i == 0) {
                dp[i] = stairs[i];
            } else if (i == 1) {
                dp[i] = dp[i - 1] + stairs[i];
            } else if (i == 2) {
                dp[i] = Math.max(stairs[i - 1], stairs[i - 2]) + stairs[i];
            } else {
                dp[i] = Math.max(dp[i - 3] + stairs[i - 1], dp[i - 2]) + stairs[i];
            }
        }

        System.out.println(dp[n - 1]);
    }
}

#algorithm #BOJ #다이나믹 프로그래밍