[Baekjoon Online Judge] 2579번: 계단 오르기

2579번: 계단 오르기

요구사항

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

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

 - 각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최대값을 구한다.

입력

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

출력

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

---

 규칙에 맞게 계단을 오르며 해당 계단들의 가중치의 최대값을 구하는 문제이다. 규칙을 잘 살펴보면 연속된 세 개의 계단은 모두 밟으면 안된다. 이 말을 다르게 해석하면 총 두 가지 경우를 추론할 수 있다.

 

 - 전전 계단까지의 최대값 + 현재 계단의 값

 - 전전전 계단까지의 최대값 + 이전 계단의 값 + 현재 계단의 값

 

 이렇게 되면 어떠한 상황이 와도 연속되는 계단을 3개 이상 밟지 않을 것이다.

 

 두 경우를 비교하여 큰 값을 dp 테이블에 저장하면 된다. 예시의 입력들을 활용하여 아래 그림으로 간단하게 그 과정들을 적어두었다. dp 테이블은 계단의 최대값을 저장하는 배열이고, stairs는 각 계단의 가중치를 나타내는 배열이다. i가 4일 때 1번 은 첫 번째 경우에 해당하고, 2번은 두 번째 경우에 해당한다.

 

6
10
20
15
25
10
20

 

 

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

public class Baekjoon2579 {

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(bufferedReader.readLine());
        int[] stairs = new int[n];
        int[] dp = new int[n];

        for (int i = 0; i < n; i++)
            stairs[i] = Integer.parseInt(bufferedReader.readLine());

        if (n == 1) {
            dp[0] = stairs[0];
        } else if (n == 2) {
            dp[0] = stairs[0];
            dp[1] = stairs[0] + stairs[1];
        } else if (n >= 3) {
            dp[0] = stairs[0];
            dp[1] = stairs[0] + stairs[1];
            dp[2] = Math.max(stairs[0] + stairs[2], stairs[1] + stairs[2]);

            for (int i = 3; i < n; i++) {
                // 첫 번째 경우와 두 번째 경우의 최대값을 dp 테이블에 저장
                dp[i] = Math.max(dp[i - 2] + stairs[i], dp[i - 3] + stairs[i - 1] + stairs[i]);
            }
        }

        /**
         * 디버깅
         */
        for (int i : dp) {
            System.out.println("i = " + i);
        }
        
        bufferedWriter.write(String.valueOf(dp[n - 1]));

        bufferedWriter.flush();
        bufferedReader.close();
        bufferedWriter.close();
    }
}

 

 dp 테이블에 값이 맞게 들어갔는지 확인하기 위해 출력해보았다.

 

6
10
20
15
25
10
20
i = 10
i = 30
i = 35
i = 55
i = 65
i = 75
75

 

 또한 n의 값이 1일 때, 2일 때 3이상 일때 모두 처리될 수 있도록 각각의 케이스를 if else로 분리하였다.

 

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

public class Baekjoon2579 {

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(bufferedReader.readLine());
        int[] stairs = new int[n];
        int[] dp = new int[n];

        for (int i = 0; i < n; i++)
            stairs[i] = Integer.parseInt(bufferedReader.readLine());

        if (n == 1) {
            dp[0] = stairs[0];
        } else if (n == 2) {
            dp[0] = stairs[0];
            dp[1] = stairs[0] + stairs[1];
        } else if (n >= 3) {
            dp[0] = stairs[0];
            dp[1] = stairs[0] + stairs[1];
            dp[2] = Math.max(stairs[0] + stairs[2], stairs[1] + stairs[2]);

            for (int i = 3; i < n; i++) {
                // 첫 번째 경우와 두 번째 경우의 최대값을 dp 테이블에 저장
                dp[i] = Math.max(dp[i - 2] + stairs[i], dp[i - 3] + stairs[i - 1] + stairs[i]);
            }
        }
        
        bufferedWriter.write(String.valueOf(dp[n - 1]));

        bufferedWriter.flush();
        bufferedReader.close();
        bufferedWriter.close();
    }
}