[Baekjoon] 계단 오르기

👀 문제 설명

문제

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

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

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

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

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

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

 

입력

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

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

 

출력

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

 

예제 입력 1

6

10

20

15

25

10

20

 

예제 출력 1

75

 

✍🏻풀이

[풀이 방법 1]

처음에는 단순하게

dp[i] = i번째 계단까지 올라섰을 때의 최댓값

으로 뒀는데, 이럴 경우 문제는 이전에 몇 계단을 연속으로 밟았는지 저장할 수 없는 것이었다.

이를 해결하기 위해서는 dp값을 이차원 배열로 정의하면 된다.

dp[i][1]은 i번째 계단까지 올라서고, 계단 1개를 연속으로 밟았을 때의 최댓값을 저장하고 (즉, i - 1은 밟지 않았다. i만 밟음)

dp[i][2]는 i번째 계단까지 올라서고, 계단 2개를 연속으로 밟았을 때의 최댓값을 저장한다. (즉, i - 1과 i를 밟고, i - 2는 밟지 않음)

i를 N까지 채운 후, 마지막에 dp[N][1]과 dp[N][2] 중, 더 큰 값을 출력하면 된다.

이 때, dp의 점화식은

dp[i][1] = max(dp[i - 2][1], dp[i - 2][2]) + stairs[i],

  -> i를 밟고, i - 1은 밟을 수 없다. i - 2는 i와 연속된 칸이 아니므로 연속된 1개를 밟든 2개를 밟든 상관이 없다.

dp[i][2] = dp[i - 1][1] + stairs[i]이다.

  -> i를 밟고, i - 1를 밟는 경우, i - 2는 밟을 수 없다. 그러므로 반드시 dp[i - 1][1]을 더해야 한다.

 

[풀이 방법 2]

이차원 배열을 사용하지 않고도 문제를 푸는 방법은 있다.

(계단을 밟을 때의 최댓값)은 (전체 계단의 합 - 밟지 않는 계단들의 최솟값)과 같으므로, 뒤의 식으로 dp값을 저장하면 된다.

dp[i]는 i번째 계단까지 봤을 경우, i번째 계단을 밟지 않고! 이전의 밟지 않은 계단들의 최솟값을 저장한다.

i번째 계단을 밟지 않으면, i - 1번째 계단은 반드시 밟아야 하고, 그럴 경우 i - 2 또는 i - 3번 계단 둘 중 하나만 밟아야 한다.

이 때, dp의 점화식은

dp[i] = min(dp[i - 2], dp[i - 3] + stairs[i]가 된다.

그리고 마지막 계단은 꼭 밟아야 하므로, 정답은 sum - min(dp[i - 1], dp[i - 2])가 되는 것이다.

 

코드

정답 1 (풀이 방법 1)

//  계단 오르기 (https://www.acmicpc.net/problem/2579)

#include <iostream>

#define MAX 301

using namespace std;

int stairs[MAX];
// 문제의 조건이 한 번에 한계단 또는 두 계단씩 오를 수 있고, 연속된 세 개의 계단을 모두 밟으면 안되므로
// 현재까지 몇 계단을 연속으로 밟았는지 저장할 수 있어야 한다.
// -> 이차원 배열 사용
/**
 * dp[i][1]에는 i까지 연속된 1개의 계단을 밟고 올라섰을 때의 최댓값 (즉, i - 1은 밟지 않았다는 소리)
 * dp[i][2]에는 i까지 연속된 2개의 계단을 밟고 올라섰을 때의 최댓값 (즉, i - 1, i를 밟았다는 소리)
 * 이 저장되어 있다.
 */
int dp[MAX][3];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);

    // input
    int N; // 계단의 개수
    cin >> N;
    
    for (int i = 1; i <= N; i++) {
        cin >> stairs[i];
    }

    if (N == 1) {
        cout << stairs[1] << "\n";
        return 0;
    }

    dp[1][1] = stairs[1]; dp[1][2] = 0;
    dp[2][1] = stairs[2]; dp[2][2] = stairs[1] + stairs[2];

    for (int i = 3; i <= N; i++) {
        /**
         * dp[i][1]는 i - 1을 밟지 않아야 하므로, dp[i][1] = max(dp[i - 2][1], dp[i - 2][2]) + stairs[i]이고,
         * dp[i][2]는 i를 밟아야 하고, i - 1을 밟지 않아야 하므로 dp[i][2] = dp[i - 1][1] + stairs[i]이다.
         */
        dp[i][1] = max(dp[i - 2][1], dp[i - 2][2]) + stairs[i];
        dp[i][2] = dp[i - 1][1] + stairs[i];
    }

    cout << max(dp[N][1], dp[N][2]) << "\n";

    return 0;
}

 

정답 2 (풀이 방법 2)

//  계단 오르기 (https://www.acmicpc.net/problem/2579)

#include <iostream>

#define MAX 301

using namespace std;

/**
 * [일차원 배열로 문제 푸는 법]
 * dp[i]를 i번째 계단까지 봤을 때, i번째 계단은 사용하지 않고, 이때까지의 사용하지 않은 계단들의 합의 최솟값
 * 이라고 하면,
 * 계단의 총합에서 사용하지 않은 계단들의 합의 최솟값을 빼면 정답이 된다.
 */
int stairs[MAX];
int dp[MAX];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);

    // input
    int N;
    cin >> N;

    int sum = 0;
    for (int i = 1; i <= N; i++) {
        cin >> stairs[i];
        sum += stairs[i];
    }

    // solve
    /**
     * i번째 계단을 사용하지 않는다는 것은
     * i - 1번째 계단은 반드시 사용한다는 뜻이고, 그럴경우
     * i - 2번째 계단 or i - 3번째 계단 중 하나만 사용한다는 뜻이다. (둘 중 하나만!)
     * 그러면 dp의 점화식은
     * dp[i] = min(dp[i - 2], dp[i - 3]) + stairs[i]
     * 가 된다.
     */
    dp[1] = stairs[1]; // 1번 계단을 사용하지 않을 때의 최솟값 = stairs[1]
    dp[2] = stairs[2];
    dp[3] = stairs[3];

    for (int i = 4; i <= N; i++) {
        dp[i] = min(dp[i - 2], dp[i - 3]) + stairs[i];
    }
    
    // 마지막 계단은 반드시 밟아야 하므로, N - 1 또는 N - 2를 밟지 않아야 한다.
    cout << sum - min(dp[N - 1], dp[N - 2]) << "\n";
    
    return 0;
}