[JAVA] 백준 2579번_계단 오르기

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

2579번: 계단 오르기

---

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

public class Main {
    static int N;
    static int[] stairs;
    static int[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        stairs = new int[N + 1];
        dp = new int[N + 1][2];
        for (int i = 1; i <= N; i++) {
            stairs[i] = Integer.parseInt(br.readLine());
        }
        if(N == 1){
            System.out.println(stairs[1]);
            return;
        }
        dp[1][0] = dp[1][1] = stairs[1];
        for (int i = 2; i <= N; i++) {
            dp[i][0] = Math.max(dp[i - 2][0], dp[i - 2][1]) + stairs[i];
            dp[i][1] = dp[i - 1][0] + stairs[i];
        }
        System.out.println(Math.max(dp[N][0], dp[N][1]));
    }
}

 

핵심 : 3개 이상의 계단을 연속해서 밟을 수 없다 → 최대 계단은 2개까지 연속 밟기 가능

즉, 현재 밟은 계단이 k번째 계단인 경우 k-2번째 계단을 밟고 밟거나(첫 번째), k-1번째 계단을 밟고 밟음(2번째)

→ dp[k] = max(dp[k-1], dp[k-2]) + stairs[k] 

• 위 점화식의 문제점
  • k-1번째 계단이 첫번째로 밟은 계단인지 알 수 없음 (k-2 → k-1 → k 인 경우 발생 가능) (= 마찬가지로 k번째 계단을 2번째로 밟은 경우, 다음 계단을 밟지 못하게 하기 불가능)
• 해결책
  • dp[k][0]에 k번째 계단을 첫번째로 밟은 경우 가능한 최대값
  • dp[k][1]에 k번째 계단을 두번째로 밟은 경우 가능한 최대값을 각각 따로 구함

---

• 다른 방법
• k-1번째 계단이 첫번째로 밟은 계단인지 알 수 없음 (k-2 → k-1 → k 인 경우 발생 가능
  • k-1번째 계단을 무조건 첫번째로 밟은 값으로 만들어서 비교 (k-3번째 계단까지 통제)
  • dp[k] = max(dp[k-3] + stairs [k-1] + stairs[k],  dp[k-2] + stairs[k]) →  k-1번째를 첫번째로 밟은 값 = dp[k-3] + arr[k-1], k-2를 밟은 값 중 최대 = dp[k-2]

좋은 풀이이니 익혀두자

출처 : https://st-lab.tistory.com/132