[BAE/<JOON> 문제풀이] 2579. 계단오르기 (DP.005)

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

2579번: 계단 오르기

계단 3개를 동시에 오를 수는 없으므로 1칸을 올랐다면 다음 움직임은 +2칸으로 확정이다.

 

또한 마지막 계단은 반드시 밟아야하므로 그냥 마지막 계단에서 역순으로 내려오는 식으로 코드를 작성했다.

 

우선 cnt배열은 단순 정수배열이 아닌, 하나의 인덱스의 2개의 값을 저장하도록 했다. 

 

i번째 계단을 밟았을 때 해당 계단의 이전 계단을 연속으로 밟았는지 여부를 파악하기 위해서이다.

 

점화식 자체는 단순하다.

 

현재 계단을 i번째 계단이라고 했을 때

 

cnt[i + 1].two, 즉 이전 계단의 2개를 건너뛴 최댓값에 arr[i] 현재 계단 값을 더해서 cnt[i].one 을 계산한다.

 

이전 계단의 1개를 건너뛴 최댓값은 계산할 필요가 없다.(3개를 연속으로 밟게 되므로)

 

cnt[i].two의 값은 cnt[i + 2]값의 one, two를 모두 고려하여 계산한다. 2계단을 건너왔으므로 2계단을 밟든, 1계단을 밟든 3개를 연속으로 밟지 않기 때문이다.

 

마지막으로 배열의 1번까지 계산했을 때 시작 계단에서 2칸을 건너 뛸 수 있으므로 cnt[1]뿐 아니라 cnt[2]의 값까지 포함하여 최댓값을 계산한다.

 

#include <iostream>
#include <vector>

using namespace std;

struct s {
    int o, t;
};

int main()
{
    vector<int> arr;    
    vector<s> cnt;
    int n;
    cin >> n;
    arr.resize(n + 3);
    cnt.resize(n + 3);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    int sum = 0;
    for (int i = 1; i <= n + 2; i++) {
        cnt[i].o = -9999999;
        cnt[i].t = -9999999;
    }
    cnt[n].o = arr[n];
    cnt[n].t = arr[n];
    for (int i = n; i >= 1; i-=1) {
        if (cnt[i].o < arr[i] + cnt[i + 1].t && cnt[i + 1].t != -9999999) {
            cnt[i].o = arr[i] + cnt[i + 1].t;//점프 1칸
        }
        int max = (cnt[i + 2].o > cnt[i + 2].t ? cnt[i + 2].o : cnt[i + 2].t);
        if (cnt[i].t < arr[i] && max != -9999999) {
            cnt[i].t = arr[i] + max;//점프 2칸
        }                
    }
    int t1 = (cnt[1].o > cnt[1].t ? cnt[1].o : cnt[1].t);
    int t2 = (cnt[2].o > cnt[2].t ? cnt[2].o : cnt[2].t);
    cout << (t1 > t2 ? t1 : t2) << endl;
    return 0;
}

 

이 문제 정올 문제라 그런지 좀 어려웠다.

 

초딩들이 이런 문제를 어떻게 푸나 진짜... 부럽구만.. 더 열심히 해야겠다