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

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

2579번: 계단 오르기

dp로 풀 수 있는 대표적인 문제이다.

 

이 문제에서 요구하는 규칙이 있다.

 

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

여기서 문제는 2번 조건이다.

다른 문제처럼 점화식을 세우려고 보니까

2번 조건 때문에 쉽게 되지 않는다.

 

여기서 한 번 더 생각해 준다.

 

보통 다른 문제들은 한 단계 이전의 값을 이용해 현재 dp값을 채웠다면

이 문제는 두 단계 이전의 값을 이용해 현재 dp값을 채운다는 것이다.

 

이 과정에서 조건 2를 만족하게 점화식을 세우는 것이다.

 

다음과 같이 dp테이블을 정의하자.

dp[i] : i번째 계단에 올랐을 때 최대 점수

 

i번째 계단까지 오르는 법은 2가지가 있다.

 

1. i-2번째 계단에서 계단 2개를 오르는 방법.
2. i-3번째 계단에서 계단 2개를 오르고 1개를 더 오르는 방법.

이를 점화식으로 나타내어 보면 다음과 같다.

dp[i] = max(dp[i-2], dp[i-3]+arr[i-1]) + arr[i]

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,dp[333],arr[333];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>arr[i];
    dp[1]=arr[1];
    dp[2]=arr[1]+arr[2];
    for(int i=3; i<=n; i++)
        dp[i] = max(dp[i-2],dp[i-3]+arr[i-1])+arr[i];
    cout << dp[n];
    return 0;
}