백준 2579번: 계단 오르기

문제

문제 바로가기> 백준 2579번: 계단 오르기

풀이

3가지 규칙을 가지고 계단을 올라 얻을 수 있는 최대값을 구하는 문제로, dp(dynamic programming) 를 이용해 풀 수 있다.

다음과 같이 초기화를 진행하고,

dp[1] = score[1]
: 첫 번째 계단 까지의 최대값은 당연히 score[1]일 것이다.

dp[2] = score[1]+score[2]
: 두 번째 계단 까지의 최대값 또한 당연히 score[1]+score[2]일 것이다.

dp[3] = max(score[1]+score[3], score[2]+score[3])
: 세 번째 계단 까지의 최대값은 연속된 3칸을 밟아서는 안되므로 score[1]+score[3] 또는 score[2]+score[3]이 될 것이다.

다음 점화식으로 dp를 진행하면 된다.

max(score[i]+dp[i-2] , score[i]+score[i-1]+dp[i-3])
: 두 계단 점프 or 한 계단 점프 (연속된 세 계단 밟지 x)

#include<iostream>
#define MAX 301
using namespace std;

int N;
int score[MAX], dp[MAX];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    // 입력
    cin>>N; 
    for(int i=1; i<=N; i++) cin>>score[i];
    
    // 초기화
    dp[1] = score[1];
    dp[2] = score[1]+score[2];
    dp[3] = max(score[1]+score[3], score[2]+score[3]);

    // dynamic programming
    for(int i=4; i<=N; i++)
        dp[i] = max(score[i]+dp[i-2] , score[i]+score[i-1]+dp[i-3]);
    
    // 정답 출력
    cout << dp[N];
}