[DP] 백준 2579번 - 계단 오르기 (코드 풀이)

[DP] 백준 2579번 - 계단 오르기

 2019년에 첫 번째로 풀어본 문제입니다. 아직 동적계획법에 대한 문제를 별로 풀어보지 않아서 1시간 가량 고민을 했습니다. 처음에는 재귀 방식으로 풀어보려 했지만 모두 다 계산하는 방식이어서 시간초과가 나버리고 말았습니다. 중복해서 계산하는 부분이 많기 때문에 이 문제는 다이나믹 프로그래밍으로 풀어야지 제 시간안에 풀 수 있습니다.

문제는 말 그대로 계단을 올라가는데

점수가 가장 높은 점수가 몇점인지 알아내야합니다.

3개의 정해진 규칙에 의해서 말이죠.

 마지막 계단에 무조건 도착을 해야 정상적으로 점수를 받을 수 있기 때문에 마지막 계단을 기준으로 해서 도달 할 수 있는 경우만 계산해야합니다.

 이 경우는 2가지로 축약 될 수 있습니다.

 도달해야 되는 곳이 N번째 계단이고,

1. N-1번째 계단을 밟고 N에 도착한 경우, N-3번째 계단을 밟았으며 N번째 계단을 밟는다.
2. N-2번째 계단을 밟고 N에 도착한 경우, N-2에서 N번째 계단을 밟고 바로 도착한다.

 이 위 두가지 경우에서 가장 높은 점수를 받는 쪽을 캐시에 저장하면서 계단을 올라가도록 하면된다.

코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

#include <iostream> #include <vector> #include <algorithm> using namespace std; vector<int> dp; int main(void) {     ios::sync_with_stdio(false);     cin.tie(NULL);     ///////////////////     int floorNum;     cin >> floorNum;     dp = vector<int>(floorNum + 1, 0);     vector<int> floors(floorNum + 1, 0);     for (int i = 1; i < floorNum + 1; ++i) {         int score;         cin >> score;         floors[i] = score;     }     dp[1] = floors[1];     dp[2] = max(floors[2], floors[1] + floors[2]);     dp[3] = max(floors[1] + floors[3], floors[2] + floors[3]);     for (int i = 4; i < floorNum + 1; i++) {         dp[i] = max(dp[i - 2] + floors[i], dp[i - 3] + floors[i] + floors[i - 1]);     }     cout << dp[floorNum] << '\n';     return 0; } Colored by Color Scripter

cs

 코드 에서 처럼 1,2,3의 경우를 먼저 계산 해놓고 재귀 형식이 아닌 for문을 사용한 DP를 구현했다. 이때 인덱스를 1부터 시작 하기 위해서 계단수의 +1한 값을 벡터의 크기로 지정했다. for문에서는 위에서 설명한 점화식을 적용하여 algorithm헤더에 있는 max를 사용하여 크기가 큰 값의 계단을 밟도록 한다.