[Baekjoon] 2579 계단 오르기 - JAVA

문제

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

<그림 1>

 

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

<그림 2>

 

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

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

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

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

---

입력

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

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

---

출력

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

---

예제 입력 1 

6
10
20
15
25
10
20

예제 출력 1 

75

 

---

📝 제출 답안

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[] stairs = new int[301];
        for (int i = 1; i <= n; i++) {
            int score = Integer.parseInt(br.readLine());
            stairs[i] = score;
        }

        int[] sum = new int[301];
        sum[1] = stairs[1];
        sum[2] = stairs[1] + stairs[2];
        sum[3] = Math.max(stairs[1], stairs[2]) + stairs[3];
        for (int i = 4; i <= n; i++) {
            sum[i] = Math.max(sum[i-3] + stairs[i-1], sum[i-2]) + stairs[i];
        }

        bw.write(String.valueOf(sum[n]));
        bw.flush();
    }
}

 

힌트를 통해 다이나믹 프로그래밍 방법으로 풀어야 한다는 것을 보고 대충 감을 잡을 수 있었다.

하지만 규칙성을 찾는게 어려워서 결국 구글링을 해야했다.

 

규칙 이해

 

규칙 이해를 위해 위 그림에서 점수 25를 n이라고 지정하고,

차례대로 내려오면서 n-1, n-2, n-3이라고 점수를 지정해준다.

 

이 상황에서 점수를 얻을 수 있는 방법은 딱 2가지가 있다.

1. n-3 과 n-1 그리고 n을 오르는 방법

2. n-2 와 n을 오르는 방법

 

이 두가지 방법 중 최댓값을 찾으면 된다.

각 계단의 점수를 저장한 배열을 stairs, 점수를 누적한 배열을 sum이라고 할 때,

이를 식으로 나타내면 다음과 같다.

sum[n] = Math.max(sum[n-3] + stairs[n-1], sum[n-2]) + stairs[n]

 

입출력 처리

BufferedReader와 BufferedWriter를 사용해 입출력 처리의 효율을 높인다.

n으로 계단의 개수를 받아오고,

stairs 배열은 각 계단의 점수를 저장하는데, stairs[0]은 사용하지 않고, 1번 계단부터 시작하여 점수를 저장한다.

계단의 최대 갯수가 300으로 지정되어 있으므로 stairs 배열의 크기는 301로 선언한다.

 

DP (다이나믹 프로그래밍)

sum 배열은 i번째 계단에 도달했을 때 얻을 수 있는 최대 점수를 저장한다.

sum[1]은 첫 번째 계단의 점수를 저장한다.

sum[2]는 첫 번째 계단과 두 번째 계단을 연속해서 밟은 점수의 합이 최대값으로 저장된다.

sum[3]은 두 가지 경우 중에 더 큰 점수를 선택해 저장한다. (stairs[1] + stairs[3] 또는 stairs[2] + stairs[3] 중 최댓값)

int[] sum = new int[301];
sum[1] = stairs[1];
sum[2] = stairs[1] + stairs[2];
sum[3] = Math.max(stairs[1], stairs[2]) + stairs[3];

 

i = 4부터 i = n까지는 DP 점화식을 이용해 최댓값을 저장한다.

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

 

i-3 에서 한 계단을 건너뛰고 현재 계단 i로 이동하는 경우와

i-2 에서 바로 현재 계단 i로 이동하는 경우 중 큰 값을 선택하도록 한다.

 

최종적으로 마지막 계단에 도달했을 때의 최대 점수 sum[n]를 bw.write 메서드로 출력한다.

이때 bw.write가 문자열만 출력 가능하므로 int 점수 값을 String.valueOf로 문자열로 바꾼 뒤 출력해준다.

bw.write(String.valueOf(sum[n]));
bw.flush();

 

 

제출 현황