[ 백준 2579 ] 계단 오르기 (C++)

백준의 계단오르기 (2579) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

주어진 규칙에 따라서 계단을 오를 때, 획득할 수 있는 점수의 최댓값을 구해야 하는 문제이다.

예시를 하나 가지고 알아보자.

7칸짜리 계단이 있고, 계단은 시작점부터 [ 1 , 2 , 3 , 4 , 5 , 6 , 7 ] 의 점수를 순서대로 가지고 있다고 가정해보자.

그리고 이 계단을 가장 아래에 있는 계단부터 올라가보자. 단 ! 문제에서는 어떤 계단을 밟고 어떤 계단을 밟지 않을수도 있지만(주어진 규칙 상 모든 계단을 다 밟을 수는 없다) 지금부터는 한 계단 한 계단씩 올라가면서 점수를 계산해볼 것인데,

그 계단을 "반드시 밟았을 때" 얻을 수 있는 최댓값을 구해보자. 지금부터 "x번 계단까지 올라갔을 때 얻을 수 있는 점수의 최댓값은?" 이라는 말은 곧, "x번 계단까지 올라왔고, 그 x번 계단을 반드시 밟았을 때, 얻을 수 있는 점수의 최댓값은 ?" 으로 해석하면 된다.

먼저, 첫 번째 계단까지 올라갔을 때 얻을 수 있는 점수의 최댓값은 얼마일까 ??

당연히 '1'일 것이다. 그럼 이 당연한 부분에서 왜 그렇게 되는지 이유를 한번 찾아보자.

우리는 지금 '1'의 점수를 가진 첫 번째 계단에 대해서 이야기를 하고 있고, 위에서 말했듯이 "첫 번째 계단을 반드시 밟았을 때의 얻을 수 있는 점수의 최댓값" 에 대해서 이야기를 하고 있다.

즉 ! 첫 번째 계단 이전에 계단은 존재하지 않고, 이 존재하지 않는다는 것을 다시 말하면 점수가 0점이라고 표현할 수 있다.

즉 ! 첫 번째 계단까지 올라왔을 때 얻을 수 있는 최대 점수는 첫 번째 계단의 점수인 '1'점이다.

[ 첫 번째 계단까지 올라왔을 때 얻을 수 있는 최대 점수 = 1 ]

두 번째 계단으로 넘어가보자. 두 번째 계단까지 올라갔을 때, 얻을 수 있는 최대점수는 몇점일까 ??

바로 '3'점이다. 왜 ? 첫 번째 계단을 밟아서 얻을 수 있는 점수(1) + 두 번째 계단을 밟아서 얻을 수 있는 점수(2) 이렇게 되어서

이 때가 두 번째 계단까지 올라왔을 때, 그리고 이 두 번째 계단을 반드시 밟았다고 가정했을 때, 얻을 수 있는 최대점수는 3점이 된다.

[ 두 번째 계단까지 올라왔을 때 얻을 수 있는 최대 점수 = 3 ]

세 번째 계단으로 넘어가보자. 세 번째 계단부터는 약간 조금 복잡해진다. 왜냐하면 문제에서 제시된 규칙중에서 "연속된 3개의 계단을 모두 밟아서는 안된다." 라는 조건 때문에 첫 번째, 두 번째 계단들과는 달리, '첫 번째 계단 + 두 번째 계단 + 세 번째 계단' 으로 계단을 오를 수 없기 때문이다.

그럼 위에서 말한대로 지금 이 상황은 "세 번째 계단을 반드시 밟아야 하는 상황" 이다. 그럼 점수를 계산하기 전에, 어떻게 계단을 올라오면 "반드시 세 번째 계단을 밟을 수 있는지" 에 대해서 부터 생각을 해보자.

세 번째 계단을 반드시 밟을 수 있는 경우는 2가지 경우가 존재한다.

1. 시작점 - 1번계단 - 3번계단

2. 시작점 - 2번계단 - 3번계단

위의 2가지 방법으로 올라오게 되면, 조건에 위배되지 않고 세 번째 계단을 밟을 수 있게 된다.

그럼 위의 2가지 경우에서 더 큰 값을 가지는 경우가, 아마 "세 번째 계단을 반드시 밟았을 때, 얻을 수 있는 최댓값"이 될 것이다.

1번 경우는 1 + 3 = 4 점이 되고 , 2번 경우는 2 + 3 = 5 로, 2번 경우가 더 큰 값을 가지므로 세 번째 계단까지 올라왔을 때 얻을 수 있는 최대 점수는 5점이 된다.

[ 세 번째 계단까지 올라왔을 때 얻을 수 있는 최대 점수 = 5 ]

네 번째 계단으로 가보자. 세 번째 계단과 마찬가지로, 네 번째 계단을 밟을 수 있는 경우에 대해서 부터 알아보자.

1. 시작점 - 1번계단 - 2번계단 - 4번계단

2. 시작점 - 2번계단 - 4번계단

3. 시작점 - 1번계단 - 3번계단 - 4번계단

위와 같이 3가지 경우가 존재한다. 그럼 위의 3가지 경우들이 각각 몇 점을 얻을 수 있는지 알아보자.

1번 경우는 1 + 2 + 4 = 7 , 2번 경우는 2 + 4 = 6 , 3번 경우는 1 + 3 + 4 = 8 이 된다. 즉 ! 4번 계단까지 올라왔을 때, 얻을 수 있는 최대 점수는 8점이 된다.

그럼 다섯번째 계단으로 넘어가기 전에, 이제는 위의 상황들에서 하나의 일반화된 식을 한번 찾아보자.

그리고 5, 6, 7번 계단들에 대해서는 그 일반화된 식을 적용시켜서 그 식이 맞는지 검토용으로 한번 계산을 해보자.

마지막으로 계산했던, 네 번째 계산을 밟는 3가지 경우를 한번 봐보자.

1. 시작점 - 1번 계단 - 2번 계단 - 4번 계단

2. 시작점 - 2번 계단 - 4번 계단

3. 시작점 - 1번 계단 - 3번 계단 - 4번 계단

위와 같이 3가지 경우가 있었는데, 1번 Case와 2번 Case에 대해서 이야기를 해보자.

1번 Case, 2번 Case에는 하나의 공통점이 있다. 바로 "2번 계단을 밟는다는 것" 이다.

그럼, 2번 계단을 반드시 밟았을 때, 얻을 수 있는 최댓값은 얼마일까 ?? 무.조.건 "첫 번째 계단 + 두 번째 계단" 을 밟는 경우이다. 왜 ?? 계단에 쓰여진 점수는 10000 이하의 자연수 이기 때문에 계단의 점수에는 0 혹은 음수가 존재하지 않는다는 것이고, 양의 정수만 존재하는 상황에서, 시작점 -> 2번 계단 으로 한 번에 두 칸을 올라가는 경우가 절대로 시작점 -> 1번 계단 -> 2번 계단 을 통해서 올라가는 경우보다 더 큰 값을 가질 수가 없기 때문이다.

즉 !! 우리는 위에서 네 번째 계단을 밟는 경우의 수를 계산할 때, 위와 같이 3가지 경우를 비교해서 값을 구했지만, 사실상 2번 Case같은 경우에는 무조건적으로 1번 Case보다 값이 작을 수 밖에 없기 때문에 절대로 2번 Case가 최댓값이 될 수는 없다.

그럼 위의 경우들을 다시한번 적어보면, 이렇게 적을 수 있다.

1. 시작점 - 1번 계단 - 2번 계단 - 4번 계단

2. 시작점 - 1번 계단 - 3번 계단 - 4번 계단

그럼 위의 2가지 Case들을 일반화를 한번 시켜보자.

먼저 1번 Case를 살펴보자. 시작점 → 1번 계단 → 2번 계단 → 4번 계단 으로 가는 순서인데, 여기서 빨강색으로 색칠된 부분을 다르게 한번 바꿔보자. 시작점 → 1번 계단 → 2번 계단 은 우리가 위에서 계산했던 "2번 계단을 반드시 밟았을 때, 얻을 수 있는 점수의 최댓값" 과 같은 결과를 가지는 부분이다. 그럼 1번 Case에서 얻을 수 있는 점수의 최댓값은 이렇게 표현할 수 있다.

1. 2번 계단을 반드시 밟았을 때, 얻을 수 있는 점수의 최댓값 + 4번 계단을 밟았을 때 얻을 수 있는 점수

다음으로 2번 Case를 한번 살펴보자. 시작점 → 1번 계단 → 3번 계단 → 4번 계단 으로 가는 순서이다.

1번 Case와 같이 시작점 → 1번 계단 → 3번 계단 → 4번 계단 에서 빨강색으로 색칠된 부분을 "3번 계단을 반드시 밟았을 때, 얻을 수 있는 점수의 최댓값" 으로 바꿀 수 있을까 ?? 아니다 ! 바꿀 수 없다. 왜?? 위에 올려서 다시 읽어보면 알겠지만,

3번 계단을 오를 때 얻을 수 있는 점수의 최댓값은 시작점 → 2번 계단 → 3번 계단으로 가는 루트이기 때문에, 빨강색으로 색칠된 부분을 "3번 계단을 반드시 밟았을 때 얻을 수 있는 점수의 최댓값" 으로 바꿀 수는 없다.

그럼 ! 있는 그대로 다시한번 바꿔보자. 시작점 → 1번 계단 이라는 것은, 다르게 말하면, "1번 계단을 밟았을 때 얻을 수 있는 점수의 최댓값"을 의미한다. 그럼 2번 Case에서 얻을 수 있는 점수의 최댓값은 이렇게 표현할 수 있다.

2. 1번 계단을 반드시 밟았을 때, 얻을 수 있는 점수의 최댓값 + 3번 계단을 밟았을 때 얻을 수 있는 점수 + 4번 계단을 밟았을 때 얻을 수 있는 점수

이렇게 바꿀 수가 있다.

그럼 ! 위에서 파랑색 글씨들에서 4번 계단이라는 단어에 '4' 대신 'N'으로 바꿔서 표현해보자. 그럼 이렇게 표현할 수 있다.

1. N - 2번 계단을 반드시 밟았을 때, 얻을 수 있는 점수의 최댓값 + N번 계단을 밟았을 때 얻을 수 있는 점수

2. N - 3번 계단을 반드시 밟았을 때, 얻을 수 있는 점수의 최댓값 + N - 1번 계단을 밟았을 때 얻을 수 있는 점수 + N번 계단을 밟았을 때 얻을 수 있는 점수

이렇게 바꿀 수가 있다. 단지, '4'대신 'N'이라는 값을 넣었을 뿐이고, 그에 맞춰서 말을 바꿨을 뿐이다.

그럼 위의 식이 다른 값에도 적용이 되는지 확인을 해보자. 다섯번째 계단으로 알아보자.

위의 식 대로라면, 다 섯번째 계단을 밟았을 때 얻을 수 있는 점수의 최댓값은 다음과 같이 2가지 경우가 발생한다.

1. 3번(N - 2) 계단을 반드시 밟았을 때, 얻을 수 있는 점수의 최댓값 + 5번(N) 계단을 밟았을 때 얻을 수 있는 점수

2. 2번(N - 3) 계단을 반드시 밟았을 때, 얻을 수 있는 점수의 최댓값 + 4번(N - 1)번 계단을 밟았을 때 얻을 수 있는 점수 +

   5번(N) 계단을 밟았을 때 얻을 수 있는 점수

1번 경우를 계산해보면, 5 + 5 = 10 이 되고 , 2번 경우는 3 + 4 + 5 = 12 가 된다.

실제로 5번 계단을 밟을 수 있는 경우를 적어보면

1. 시작점 → 1번계단 → 2번계단 → 4번계단 → 5번계단 : 1 + 2 + 4 + 5 = 12

2. 시작점 → 1번계단 → 3번계단 → 5번계단 : 1 + 3 + 5 = 9

3. 시작점 → 2번계단 → 3번계단 → 5번계단 : 2 + 3 + 5 = 10

4. 시작점 → 2번계단 → 4번계단 → 5번계단 : 2 + 4 + 5 = 11        

이렇게 4가지 경우가 존재한다. 그 중 최댓값은 12가 된다. 즉 ! 위의 경우를 다 적어보면 4가지 경우가 나오고, N값이 커질수록 더 많은 경우가 발생할 수 있다. 그런데 ! 위에서 했던 과정처럼 중복된 과정 혹은 같은 결과값을 가지는 과정들이 포함되어 있을 것이고 결국에는 위에서 언급한 2가지 경우로 줄여낼 수 있다. 그리고 그 2가지 경우 중 더 큰 값이 최댓값이 된다.

실제로 다섯 번째 계단에서 검토를 해보니, 4가지 경우든, 2가지 경우든 결과값이 '12'로 동일하다는 것을 확인할 수 있다.

이를 코드로 구현하기 위해서 본인은 1차원 배열 하나를 사용해서 표현해 주었다.

바로 int DP[] 라는 배열인데, DP[a] = b 의 의미는 "a번째 계단을 반드시 밟았을 때, 얻을 수 있는 점수의 최댓값은 b점입니다." 를 의미한다.

그리고 DP[N]의 값을 구하기 위해서는 2가지 경우를 비교해주면 된다.

DP[N - 2] + Stair[N]

DP[N - 3] + Stair[N - 1] + Stair[N]

여기서 'Stair'이라는 변수는 계단의 점수들을 저장해놓은 배열을 의미한다.

마지막으로 ! 우리는 모든 값들을 계산할 때, "해당 계단을 반드시 밟았을 때, 얻을 수 잇는 점수의 최댓값" 을 계산했었는데 이 이유는 "마지막 도착 계단은 반드시 밟아야 한다" 라는 조건 때문이다. 즉 ! 우리는 위의 점화식을 토대로 값을 구한 후 최종적으로 DP[N]의 값을 출력을 하면 그 값이 정답이 된다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 310
using namespace std;
 
int N;
int Stair[MAX];
int DP[MAX];        // 각 계단에 서 있다고 가정했을 때, 얻을 수 있는 최댓값을 저장.
 
int Max(int A, int B) { if (A > B) return A; return B; }
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> Stair[i];
}
 
void Solution()
{
    DP[1] = Stair[1];
    DP[2] = Stair[1] + Stair[2];
    for (int i = 3; i <= N; i++)
    {
        DP[i] = Max(DP[i - 3] + Stair[i] + Stair[i - 1], DP[i - 2] + Stair[i]);
    }
    cout << DP[N] << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}