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

2579번: 계단 오르기 (acmicpc.net)

문제 해석

• dp를 이용한 최대값 찾기

알고리즘 분류

• dp

풀이

• 점화식 dp[i] = max(dp[i - 3] + arr[i - 1] + arr[i], dp[i - 2] + arr[i])를 이용해 dp배열을 채운다

코드

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

int n;
vector<int> arr;
int dp[301];

int main() { 
  cin >> n;
  arr.resize(n + 1);

  for (int i = 1; i <= n; i++) {
    cin >> arr[i];
  }
  // 초기값 설정
  dp[1] = arr[1];
  if (n > 1) {
      dp[2] = arr[1] + arr[2];
  }
  if (n > 2) {
      dp[3] = max(arr[1] + arr[3], arr[2] + arr[3]);
  }

  // dp 배열 채우기
  for (int i = 4; i <= n; i++) {
      dp[i] = max(dp[i - 3] + arr[i - 1] + arr[i], dp[i - 2] + arr[i]);
  }
  cout << dp[n];
}