[P&B] #113 BAEKJOON 2759

백준 2759번 JAVA 계단오르기

문제 설명

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

<그림 1>

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

<그림 2>

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

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

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

 

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

 

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

 

나의 문제 풀이 코드

import java.io.*;
public class bj2579 {
    static Integer dp[];
    static int arr[];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

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

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

        dp[0] = 0;    // 초기화: 계단이 0개인 경우 점수는 0
        dp[1] = arr[1];

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

        System.out.println(find(N));

    }

    static int find(int N) {
        // 아직 탐색하지 않는 N번째 계단일 경우
        if(dp[N] == null) {
            // 현재 계단을 밟을 때와 현재 계단을 밟지 않을 때 중 더 큰 점수를 선택
            dp[N] = Math.max(find(N - 2), find(N - 3) + arr[N - 1]) + arr[N];
        }

        return dp[N];
    }
}

 

문제 풀이 코멘트

이 문제는 동적 프로그래밍(Dynamic Programming)을 사용하여 해결하는 전형적인 예시입니다. 동적 프로그래밍은 작은 부분 문제의 해결을 통해 큰 문제를 해결하는 알고리즘 기법입니다. 이 문제를 해결하기 위해 다음과 같은 동적 프로그래밍의 개념을 사용합니다.

• 점화식(Recurrence Relation): 큰 문제를 작은 부분 문제로 분해하고, 작은 부분 문제의 해결을 통해 큰 문제를 풀어나가는 방법을 정의합니다.
• 메모이제이션(Memoization): 중복 계산을 피하기 위해 이전에 계산한 결과를 저장하고 재활용하는 방법입니다.

계단 오르기 문제는 아래와 같이 풀이해야합니다.

1. 각 계단을 오르면 점수를 얻을 수 있으며, 한 번에 하나 또는 두 개의 계단을 오를 수 있습니다.
2. 연속된 세 개의 계단을 모두 밟으면 안 되므로, 세 개의 연속된 계단을 밟지 않고 최대 점수를 얻는 방법을 찾아야 합니다.
3. 마지막 계단은 반드시 밟아야 하므로, 마지막 계단을 기준으로 역으로 거슬러 올라가며 최대 점수를 계산해야 합니다.

코드에서 가장 중요한 부분들만 설명을 적어보자면 다음과 같습니다.

먼저, dp 배열은 계단의 개수 N에 대응하는 메모이제이션 배열입니다. dp[N]은 N개의 계단까지 오를 때 얻을 수 있는 최대 점수를 저장합니다.
재귀함수 호출하기 전 dp 배열을 초기화 해야합니다.
dp[0]을 0으로 초기화하는 이유는, 0개의 계단일 때 얻을 수 있는 점수는 0이기 때문이고 dp[1]과 dp[2]를 초기화하는 이유는, 각각 1개의 계단과 2개의 계단을 오를 때 얻을 수 있는 최대 점수를 계산하기 위함입니다.
2개의 계단까지 오를 때 얻을 수 있는 경우의 최대 점수를 초기화를 했으면 find라는 메서드를 호출합니다.

find 메서드는 재귀적으로 동적 프로그래밍을 수행하며, N개의 계단까지 오를 때 얻을 수 있는 최대 점수를 계산하고 반환합니다. 즉 아직 탐색하지 않은 N번째 계단일 경우, 두 가지 선택 중 더 큰 점수를 선택하고 dp[N]에 저장합니다.

• if(dp[N] == null) 부분은 아직 계산하지 않은 N번째 계단의 경우입니다. 초기에 dp 배열은 모두 null로 초기화되어 있으므로, dp[N]이 null이라면 아직 이 위치의 최대 점수를 계산하지 않았다는 것을 의미합니다.
• dp[N]는 N번째 계단에서 선택할 수 있는 두 가지 옵션 중에서 더 큰 값을 선택합니다.
  • 첫 번째 옵션: N-2번째 계단에서 두 계단을 올라오는 경우 =  N번째 계단을 밟았을 때의 경우, N-2 계단까지의 최대 점수 + N-2 계단의 점수 (연속된 세 계단을 피하기 위해 N-1번째 계단을 건너뛰어야 함)
  • 두 번째 옵션: N-3번째 계단에서 한 계단을 올라오고 N-1번째 계단에서 한 계단을 올라오는 경우 = N번째 계단을 밟지 않았을 때의 경우, N-3 계단까지의 최대 점수 + N-1 계단의 점수
  • 이 두 옵션 중에서 얻을 수 있는 최대 점수를 선택하고 N번째 계단의 점수를 더합니다.
• dp[N]를 계산하고 반환합니다.

find 메서드는 재귀적으로 호출됩니다. 호출된 메서드는 N-1번째 계단 또는 N-2번째 계단에 도달했을 때 얻을 수 있는 최대 점수를 계산하고, 이를 반환합니다. 그리고 그 값을 기반으로 N번째 계단에 도달했을 때 얻을 수 있는 최대 점수를 계산합니다. 이러한 과정이 반복되어서 find(N)을 호출하면, 최종적으로 N번째 계단까지 도달했을 때 얻을 수 있는 최대 점수가 계산됩니다.