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

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

( 문제 바로가기 )

( 문제를 다시 푸는 과정에서 보다 상세한 설명을 다시 포스팅 해놓았습니다. 이 글을 읽으셔도 무관하지만, 보다

  구체적인 설명을 원하시는 분들은 아래의 링크를 타고 가시면 됩니다 ! )

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

[ 문제설명 ]

- 입력으로 계단의 총 갯수와, 각 계단마다 점수가 주어진다.

- 계단을 올라야 하는데, 마지막 도착계단은 반드시 밟아야 하며, 연속된 세개의 계단을 밟아서는 안된다.

  또한, 한 번에 한 계단 혹은 두 계단씩 오를 수 있다.

- 계단을 오르면서 얻을 수 있는 가장 큰 점수를 구하면 된다.

[ 문제풀이 ]

1) 계단의 점수를 입력받는 배열 Arr와 계단의 최댓값을 저장하는 배열 DP 2개의 배열을 사용했다.

2) Arr[a] = a층 계단의 점수, DP[a] = a층 계단 까지의 최댓값을 의미한다.

3) 본인은 배열의 0번을 사용하지 않았고, 1번 Index부터 1층으로 계산을 했다.

4) 도출해낼 수 있는 초기값을 생각해보면 

   DP[1] = Arr[1] ( 1번 계단 까지의 최댓값은 당연히 1번 계단의 점수 )

   DP[2] = Arr[1] + Arr[2] ( 2번 계단 까지의 최댓값은 1번계단의 점수 + 2번계단의 점수 )

   - 위의 식은 조건에 위배되지도 않고, Arr[2]가 Arr[1]+Arr[2]보다 절대 클 수가 없기 때문에(점수 = 300보다 작은 자연수)

     성립한다.

   DP[3] = ?? 3번째 계단까지의 최댓값은 생각해보면 DP[1], DP[2]와 같이 하나의 값이 아니다.

   3번째 계단까지의 최댓값은 = " 1번계단 + 두 계단 올라간 3번계단" or "두 계단 올라간 2번 계단 + 3번 계단" 둘 중

   더 큰 값이 된다.

   그럼 4번째 계단의 경우는 어떻게 될까....

   DP[4]의 경우에는 2번계단까지의 최댓값 + 4번계단(3번계단을 밟으면 3개 연속해서 밟는 것이므로 안됨)
   혹은 1번계단까지의 최댓값 + 3번계단 + 4번계단이 된다.

   그렇다면 N번계단은??

   DP[N]의 경우 "N-2번 계단 까지의 최댓값 + N번계단" or "N-3번 계단까지의 최댓값 + N-1번계단 + N번계단" 이

   될 것이다.

5) 4)의 이론을 점화식으로 도출해내보면

   DP[N] = DP[N-2] + Arr[N] vs DP[N-3] + Arr[N-1] + Arr[N] 이 된다.

6) 포도주 시식(백준 - 2156) 문제와 달리, 마지막 계단을 반드시 밟아야 하므로(포도주시식은 마지막 잔을 안먹는 경우 고려)

   그 점만 주의한다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 301
using namespace std;
 
int N;
int Arr[MAX];    // 계단을 나타내는 배열
int DP[MAX];    // 해당 계단까지의 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 >> Arr[i];
    }
}
 
void Solution()
{
    DP[1] = Arr[1];    // 첫 번째 계단까지의 Max 값은 첫번째 계단 값이지
    DP[2] = Arr[1] + Arr[2];
    DP[3] = Max(Arr[1] + Arr[3], Arr[2] + Arr[3]);
    
    for (int i = 4; i <= N; i++)
    {
        DP[i] = Max(DP[i - 2] + Arr[i], DP[i - 3] + Arr[i-1] + Arr[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;
}