[백준] 2579번: 계단 오르기

 

 

---

 

문제

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

 

개념

DP(다이나믹 프로그래밍)

 

 

실행 결과

 

 

 

 

 

구현 코드(c++)

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  int n;
  cin >> n;

  vector<long long> v(n + 1); // 계단 별 점수 배열

  for (int i = 1; i <= n; i++) {
    cin >> v[i];
  }

  vector<long long> dp(n + 1, 0); // 총 점수 배열

  dp[1] = v[1];
  dp[2] = v[1] + v[2];
  dp[3] = max(v[1] + v[3], v[2] + v[3]);

  for (int i = 4; i < n + 1; i++) {
    // 두 계단을 건너뛴 경우 or 한 계단만 건너뛴 경우
    dp[i] = max(dp[i - 2] + v[i], dp[i - 3] + v[i - 1] + v[i]);
  }

  cout << dp[n];

  return 0;
}

 

 

 

 

코드 설명

일단 dp 배열을 선언하고, 계단을 하나씩 오른다고 생각해본다.

 

dp[1] = 첫번째 계단

dp[2] = 첫번째 계단 + 두번째 계단

dp[3] => 여기서부터 계단을 오르는 방법이 다음과 같이 두 종류로 나뉜다.

다음 계단을 건너뛸것인지 그냥 바로 오를것인지!

즉, 3번째 계단에서 얻을 수 있는 점수의 최댓값은 max(v[1] + v[3], v[2] + v[3])가 될 것이다.

 

따라서 이 법칙에 따라 점화식을 세우면 다음과 같다.

dp[i] = max(dp[i - 2] + v[i], dp[i - 3] + v[i - 1] + v[i]);

 

두 계단을 건너 뛴 경우 or 한 계단만 건너 뛴 경우 중 더 큰 값을 취하도록 한다.

후자에서 dp[i-3]인 이유는 문제에서 세 계단을 연속해서 밟을 수 없기 때문에 네번째 전 dp합을 더해야 함.

 

 

 

 

---