[백준 / BOJ] C++ 2579 계단 오르기

2579번: 계단 오르기

 

문제

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

2579번: 계단 오르기

 

 

풀이

계단은 1칸 또는 2칸 이동가능하며 연속된 3개의 계단을 오를 수는 없다. 그리고 마지막 계단은 반드시 밟아야 한다. 얻을 수 있는 포인트의 최댓값을 구하는 문제.

dp로 해결가능하다. dp[i]는 i번째 계단까지 가는 경우의 포인트의 최댓값이며 v[i]는 i번째 계단을 밟았을 때 얻는 포인트다.

 

1번째 계단까지의 최댓값은 dp[1] = v[1] 이다.

 

2번째 계단까지 가는 경우는 1번째 계단에서 1칸 이동하여 가는 경우와 2칸 이동하여 바로 가는 경우다. 이 경우 최댓값은 반드시 1번째 계단을 거쳐 가는 경우이므로 dp[2] = v[1] + v[2] 이다.

 

3번째 계단까지 가는 방법은 2번째 계단에서 1칸 이동하여 가는 경우와 1번째 계단에서 2칸 이동하여 가는 경우다. 2번째 계단의 최댓값은 1번째, 2번째 계단을 거쳐 간 경우이므로 여기서 3번째 계단을 가면 연속된 3개의 계단을 갈 수 없다는 조건을 위반한다. 따라서 1번째 계단과 2번째 계단 중 최댓값 + 3번째 계단의 획득 포인트인 dp[3] = max(v[1], v[2]) + v[3] 이 된다.

 

4번째 계단까지 가는 방법은 2번째 계단에서 2칸 이동하는 경우와 3번째 칸에서 1칸 이동하는 경우가 있다. 다만 후자는 연속된 3칸을 이동할 수 없다는 조건을 만족시키기 위해서 이전에 2칸 이동을 했어야만 한다. 따라서 2번째 칸에서 2칸 이동하는 경우와 1번째 칸에서 2칸 이동하여 3번째 칸으로 간 후 1칸 이동하는 경우 두 가지다. 이를 식으로 나타내면 dp[4] = max(dp[2], dp[1] + v[3]) + v[4] 이다.

 

이후는 4번째 계단과 같은 방식으로 진행할 수 있다. 이를 점화식으로 나타내보면 dp[i] = max(dp[i-2], dp[i-3] + v[i-1]) + v[i] 이다. 그러므로 마지막 계단을 밟았을 때, dp 배열의 마지막 값이 정답이 된다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  cin >> n;
  vector<int> dp(n + 1, 0), v(n + 1);
  for (int i = 1; i <= n; i++)
    cin >> v[i];
  dp[1] = v[1];
  dp[2] = v[1] + v[2];
  dp[3] = max(v[1], v[2]) + v[3];
  for (int i = 4; i <= n; i++)
    dp[i] = max(dp[i - 3] + v[i - 1], dp[i - 2]) + v[i];
  cout << dp[n] << '\n';
  return 0;
}