[BOJ/C++]2579번 계단오르기

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

---

문제

계단을 밟으면 그 계단의 점수를 얻음. 이 점수의 최댓값을 찾는 문제.

다만

1. 계단은 한번에 한칸 혹은 두칸 오를 수 있음.
2. 연속된 세칸 오르면 안됨(시작점은 포함x).->ex: <그림1>에서 10,20,15를 밟으면 안됨. 10,20,25는 ok
3. 마지막 계단은 모두 밟아야  함.

풀이

arr[n+1]에 계단의 점수를 받고 dp[n+1]에 i번째 계단을 밟았을 때 최댓값을 넣었다. 그래서 마지막에 dp[n]을 출력한다.

먼저 dp[1]에는 arr[1], 즉 <그림1>로 따지면 10을 넣어주었고

dp[2]에는(최댓값이므로) dp[1]+arr[2]를 넣어주었다.

그 후 i번째 계단을 밟았을 경우를 가정해서 가능한 경우를 모두 비교해주었다.

 

직전 계단을 밟은 경우는 연속 세칸이 불가능하므로 dp[i-3]+arr[i-1]계단을 밟은 후 arr[i]번째를 밟았을 것이다.

 

 

직전 계단을 밟지 않은 경우는 dp[i-2]번째 계단을 밟고 arr[i]를 밟았을 것이다.

따라서 dp[i-3]+arr[i-1]와 dp[i-2]를 비교해서 둘 중 더 큰걸 arr[i]와 더해주어 dp[i]에 저장했다.

 

소스코드

#include<iostream>
using namespace std;

int main(void){
    int n;cin>>n;
    int arr[n+1];
    for(int i=1;i<n+1;i++)
        cin>>arr[i];
    
    int dp[n+1];
    dp[0]=0;dp[1]=arr[1];dp[2]=dp[1]+arr[2];
    for(int i=3;i<=n;i++){
        if(dp[i-2]<arr[i-1]+dp[i-3])//직전계단+i-3번째 계단이 i-2번째 계단까지 올라간수보다 크면
            dp[i]=arr[i]+arr[i-1]+dp[i-3];
        else
            dp[i]=arr[i]+dp[i-2];
    }
    cout<<dp[n]<<endl;
}