[백준 알고리즘] 2579번 - 계단오르기 (Dynamic programming)

1. 문제 및 예시 실행 결과

 

 중구난방으로 알고리즘 문제를 풀다 이러면 아무것도 안 될 것 같아서 내가 약한 유형의 문제를 우선적으로 공부해야겠다는 생각해 DP문제를 쭉 풀어보았다. 바킹독님의 블로그에서 공부하고 있는데 풀이가 달라 한 번 정리해보았다.

 

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

---

---

2. 본문

 

 DP는 데이터 구조를 먼저 생각해보고 점화식을 세우는 두가지의 단계로 나뉜다고 생각한다. 물론 점화식을 세운다는 것 자체가 안 되는 문제이기에 구현 다음으로 손에 익어야하는 문제가 아닌가 싶다. 어쨎든 해당 문제의 데이터 구조와 점화식은 다음과 같이 정했다.

---

데이터 구조: cache[i] = i번째 계단으로 얻을 수 있는 점수 중 최대값.

---

 이제 데이터 구조를 구하는 점화식을 세우기만 하면 된다.

 

 연속된 세개의 계단을 전부 밟지 않아야한다는 조건을 만족하면, 지금 계단의 최대값은 다음과 같이 구할 수 있다.

---

N번째 계단의 최대값: N - 1번째 계단의 점수와 N - 3번째 계단의 최대 점수를 더한 값과 N - 2번째 점수 중 최대값.

점화식: cache[i] = max(cache[i - 3] + stairs[i - 1], cache[i - 2]) + stairs[i];

---

코드는 다음과 같다.

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(void){
    vector<int> stairs;
    vector<int> cache;
    int N, s;
    cin >> N;

    for(int i = 0; i < N; i++){
        cin >> s;
        stares.push_back(s);
        cache.push_back(s);
    }

    for(int i = 1; i < N; i++){
        if(i == 1){
            cache[i] = stairs[i] + cache[i - 1];
        }
        else if(i == 2){
            cache[i] = max(stairs[i - 1], cache[i - 2]) + stairs[i];
        }else{
            cache[i] = max(cache[i - 3] + stairs[i - 1], cache[i - 2]) + stairs[i];
        }
    }

    cout << cache[N - 1];

    return 0;

}

 

 

3. 결어

 

 DP고수 되고 싶다. 골드문제를 30분 안에 푸는 정도로... 연습밖에 방법이 없을 것 같다.