백준 2579 계단 오르기 [c++]

계단오르기 실버3

문제

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

계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

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

문제 풀이

dp문제 계단의 점수를 입력받는 arr와 해당 계단의 최댓값을 저장하는 dp배열 2개를 이용.(0이 아닌 1부터 사용)

• step 1 :
  • dp[1] = arr[1]
  • 1번 계단 까지의 최대는 당연히 1번 점수
• step 2 :
  • dp[2] = arr[1] + arr[2]
• step 3 :
  • 1번계단 + 두 계단 올라간 3번계단” or “두 계단 올라간 2번 계단 + 3번 계단” 중 큰 값.
• step 4:
  • “2번까지 최대 + 4번” or “1번까지 최대 + 3 + 4번” 중 큰 값.
• 점화식 : “n-2번 계단 까지 최대값 + n번” or “n-3번까지 최대 + n-1 + n번” 중 큰 값.
• dp[n] = max(dp[n-2] + arr[n], dp[n-3] + arr[n - 1] + arr[n])

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int dp[302];
int arr[302];

void up_stair(int n)
{
    dp[1] = arr[1];
    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]);
    }
}

int main(){
    int n;
    cin >> n;

    for(int i = 1; i <= n; i++)
    {
        cin >> arr[i];
        dp[i] = 0;
    }
    
    up_stair(n);

    cout << dp[n] << endl;

    return 0;
}

총평

• 점화식만 잘 쓰면 쉽게 풀리는 문제
• 처음에 dp로 안풀고 greedy로 접근했음
• 예제는 맞게 나왔지만 반례 존재했음
• n이 크지않고 문제가 동일한 하위 문제를 반복적으로 계산하므로 DP가 적합!!

• ps
• dp