백준 - 2579번(계단 오르기)

문제 출처: https://www.acmicpc.net/problem/2579

문제

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

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

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

• 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
  연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
  마지막 도착 계단은 반드시 밟아야 한다.
  따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

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

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

public class Main {

    private static int[] stairs;
    private static int[] scores; // 메모이제이션 용

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        stairs = new int[N + 1]; // 각 계단별 점수 저장용
        scores = new int[N + 1]; // 계단별까지의 최댓값 저장용
        Arrays.fill(scores, -1);
        for (int i = 1; i <= N; i++) {
            stairs[i] = Integer.parseInt(reader.readLine());
        }

        scores[0] = stairs[0]; // dummy 값
        scores[1] = stairs[1]; // 1번 계단까지의 최댓값은 그냥 1번 계단의 수

        if (N >= 2) scores[2] = stairs[1] + stairs[2]; // 들어오는 수는 자연수로, 1이 들어올 때를 대비하여 처리. 2번 계단까지의 최댓값

        System.out.println(dynamicPrograming(N));
    }

    private static int dynamicPrograming(int stair) {
        if (scores[stair] == -1) { // 아직 값이 등록이 안 된 경우
            scores[stair] = Math.max(dynamicPrograming(stair - 2), dynamicPrograming(stair - 3) + stairs[stair - 1]) + stairs[stair];
        }

        return scores[stair];
    }
    
}

• 동적계획법의 세계에 발을 딛게 해준 첫 문제이다.
• 동적계획법을 어렴풋이 알고 있었으나 개념을 정확히 알지 못해 문제에 적용하지 못했다. 위 코드는 구글링한 결과로 작성한 것이다. 아마 개념을 알고 있었어도 풀지 못했을 것 같다... 이번 문제를 통해 동적계획법을 알게 되었고, 메모이제이션을 사용하는 방식을 알게 되었다.