문제 출처

단계별로 풀어보기 > 동적 계획법 1 > 계단 오르기
https://www.acmicpc.net/problem/2579

문제 설명

다음 3가지 규칙을 주의하여 계단을 올라갈 때, 얻을 수 있는 최댓값을 구하라.
1. 계단은 한 칸 or 두 칸을 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

접근 방법

연속된 세 개의 계단을 밟으면 안되므로, 현재 칸으로부터 2칸 전 점수 총합과 현재 칸으로부터 1칸 전 계단 점수 + 3칸 전 점수 총합을 비교하여 더 큰 값을 현재 칸과 더하여 저장하는 방식으로 진행한다.

import java.io.*;

public class 계단_오르기 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

        int dp[] = new int[N+1];
        int arr[] = new int[N+1];

        for(int i = 1; i <= N; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        dp[1] = arr[1];

        if(N >= 2){
            dp[2] = arr[1] + arr[2];
        }

        for(int i = 3; i <=N; i++){
            dp[i] = Math.max(dp[i-2], dp[i-3] + arr[i-1]) + arr[i];
        }

        bw.write(String.valueOf(dp[N]));
        bw.flush();
        bw.close();
        br.close();
    }
}

알게된 점

시간 복잡도는 O(N)이다.

문제푼 흔적