[백준] 2579번: 계단 오르기 풀이 및 해설(C++)

문제 이미지

입력

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

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

 

 

풀이

입력조건에 중요한 단서가 있다. 계단에 써져 있는 수는 모두 자연수다. 즉, 계단은 밟을 수 있다면 밟는게 일단 이득이라는 뜻이다.

하지만 3연속으로 밟을 수는 없으니 더 큰 점수를 위해 때로는 연속으로 가지 말아야 한다.

 

계단에 각 숫자가 몇이 써져 있는지 나와있는 입력배열을 arr [n]

n번째 계단까지 올랐을 때 얻게 되는 점수의 최댓값 배열을 sum [n]이라고 하자.

 

sum [n]은

1. sum [n-2]+arr [n] (n-2번째 계단의 최대점수에서 점프한 것)

2. n-2번째 계단을 밟지 않은 채 n-1번째 계단에서 점프한 것 + n계단의 값

 

둘 중의 큰 수이다.

 

그런데 2번 문장을 달리 말하면

" n-2번째 계단을 밟지 않은 n-2번째 계단까지의 최댓값 + n-1 계단의 값+n계단의 값"이고

이는: n-3번째 계단까지의 최댓값 + n-1계단의 값+n계단의 값

2번을 그러면 식으로 표현하면 sum [n-3]+arr [n-1]+arr [n]이다.

 

즉, sum [n]= max(sum [n-2]+arr [n], sum [n-3]+arr [n-1]+arr [n])이라는 식이 나온다. 

 

n-3이라는 인덱스가 존재하니 동적계획법의 베이스가 되는 n=3까지의 인덱스만 먼저 채우고 이후는 점화식으로 계산해 나간다.

 

 

해답 코드

#include <iostream>
#include <algorithm>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;


int main(){
    fastio;
    int n;
    long long stair[301];
    long long dp[301];
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>stair[i];
    }
    dp[0]=stair[0];
    dp[1]=stair[0]+stair[1];
    dp[2]=stair[2]+max(stair[0],stair[1]);
    for(int i=3; i<n; i++){
        dp[i]=max(dp[i-2]+stair[i],dp[i-3]+stair[i-1]+stair[i]);
    }
    cout<<dp[n-1];
    

}

헤맸던 부분

배열 이름을 max라고 지었다가 내장함수랑 혼동이 와서 이름을 바꾸었다.