[c++][BOJ][2579] 계단 오르기

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

2579번: 계단 오르기

각 계단에 가중치가 있고 , 꼭대기에 갔을 때 가장 큰 점수를 얻는 경우를 구하는 문제입니다.

 

일반 다이내믹 프로그래밍으로 풀려고 했으나 , 연속된 3개의 계단을 밟지 못하는 경우가 있습니다.

 

그래서 생각한게 

1. 3번째 전 칸을 밟고 연속 2개의 계단을 밟는 경우 , 

2. 2번째 전 칸을 밟고 한칸 띄어서 이번 계단을 밟는 경우

 

두 경우를 비교하려고 합니다. 이 과정에서 기본 계단의 가중치는 그대로여야 하기 때문에 , 벡터를 두개 사용하도록 하겠습니다.

 

2번째 전 까지 온 최대값 + 현재 칸의 점수 vs 3번째 전까지 최대값 + 이전칸 + 이번 칸 

 

이렇게 비교해서 최대값을 리턴합니다.

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n;
    cin >> n;
    
    vector<int> arr(n+1 , 0);
    vector<int> stair(n+1 , 0);
    
    for(int i=1; i<=n; i++){
        cin >> arr[i];
    }
    
    stair[1] = arr[1];
    stair[2] = arr[1] + arr[2];
    stair[3] = max(arr[1] + arr[3] , arr[2] + arr[3]);
    
    for(int i=4; i<=n; i++){
        stair[i] = max(stair[i-2] + arr[i], stair[i-3] + arr[i-1] + arr[i]);
    }
    
    cout << stair[n];
}