[알고리즘 PS] 백준 2579 계단 오르기 자바 문제 풀이

문제

해당 포스팅은 백준의 2547번 계단 오르기 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

해결법

이 문제는 포도주 시식 문제와 제법 유사한 문제이다.

 

하지만 정답 비율이 35 %나 되는데, 그건 간과할 수 있는 조건이 하나 있어서 이다.

자세한 것은 아래에서 설명하겠다.

접근법

여기서 출력인 계단 점수의 최대값은 무조건 마지막 계단에서 발생해야 한다.

 

그럼 마지막 계단은 꼭 밟아야 한다는 소리이다.

그럼 마지막 계단을 꼭 밟을 경우는 몇가지 일까?

 

n 개의 계단이 있을 때, 마지막 계단을 꼭 밟을 경우 2가지를 생각해보자.

1. n-1번째 계단을 밟고 오는 경우
2. n-2번째 계단을 밟고 오는 경우

 

n-1번째 계단을 밟고 오는 경우

이 경우는 n-2번째 계단을 건너 뛰고 오는 경우여야 한다.

그렇지 않으면 3개의 계단을 연속적으로 밟고 오는 것이 되므로 n-3, n-1, n 이 되어야 한다.

마지막 계단 + 전전 계단의 최대값

 

n-2번째 계단을 밟고 오는 경우

이 경우는 n-1번째 계단을 밟지 않는 경우이다.

그럼 n-2번째 계단에서 바로 n번 계단으로 가는 경우인 것이다.

전전 계단의 최대값

이 두 경우의 최대를 현재 밟고 있는 계단의 최대로 지정해주면 된다.

오답 후보

해당 문제의 정답률이 35%인 가장 큰 이유는 바로 첫 번째 계단이다.

문제에서는 첫 번째 계단을 무조건 밟으라는 이야기가 없다.

하지만 첫 번째 계단을 밟으면 무조건 이득처럼 느껴진다.

왜? 시작점은 계단에 포함되지 않는다고 했으니까.

근데 중요한건 시작점이 계단이 아니라는 것이지 첫 번째 계단을 카운팅하지 않겠다는 소리는 아니다.

 

그래서 결국 첫 번째 계단을 밟지 않는 경우가 이득일 수 있다.

 

arr = { 1,   100,   200,   300} 만 봐도 arr = { 1,   100,   200,   300} 인게 확실히 이득이다

정답 코드

import java.io.*;

public class Main {
    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[] arr = new int[301];
        int[] dp = new int[301];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        dp[0] = arr[0];
        dp[1] = Math.max(arr[1], arr[0] + arr[1]);
        dp[2] = Math.max(arr[1] + arr[2], arr[0] + arr[2]);

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

        bw.write(String.valueOf(dp[n-1]));
        bw.flush();
        bw.close();
    }
}

---

문제 회고

이번 문제는 무조건 첫 번째 계단을 밟는게 이득이겠지 하는 부족한 사고로 5번이나 틀렸었다.
점화식 도출 자체는 어렵지 않으나 왜 정답률이 낮은지 알 수 있는 문제

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.