백준 2579 (계단 오르기) c++

문제

2579번: 계단 오르기

계단을 1계단이나 2계단 오를 수 있는데 최종적으로 n번째 계단에 도달했을 때 획득 할 수 있는 최대점수를 구하는

문제 입니다.

연속적으로 3계단을 밟는건 불가능합니다.

 

여기서 상태(status)를 표현하는 방법으로 2차원 배열을 사용하였습니다.

현재 밟고 있는 계단이 이전에 1계단을 밟고 왔는지, 2계단을 밟고 왔는지 표현해 주어야합니다.

예를 들어 dp[n][k] 라는 의미는 현재 n번째 계단에 있는데 k계단을 밟고 왔다는 의미입니다.

 

여기서 점화식을 세워주면

dp[n][1] 는 2계단을 점프해 왔으므로 max(dp[n-2][1], dp[n-2][2]) + 현재 서있는 계단의 점수

dp[n][2] 는 1계단을 점프해 왔으므로 dp[n-1][2]는 제외시켜줘야 합니다. 왜냐하면 3계단을 연속적으로 밟게 되기 때문입니다. 따라서 dp[n][2]는 dp[n-1][1] + 현재 서있는 계단의 점수 입니다.

 

base case는 시작점(dp[0]= 0)입니다.

---

전체 코드입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
#include<cstring>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int dp[301][3];
int chair[301];
int n;
int cnt = 0;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n;
    for (int i = 1, c; i <= n; i++) {
        cin >> c;
        chair[i] = c;
    }
    dp[0][0] = 0;
    dp[1][1] = chair[1];
    for (int i = 2; i <= n; i++) {
        dp[i][1] = max(dp[i - 2][1], dp[i - 2][2]) + chair[i];
        dp[i][2] = dp[i - 1][1] + chair[i];
    }
    
 
    cout << max(dp[n][1], dp[n][2]);
 
    return 0;
}