[C++] BOJ 2579 계단 오르기

 

 

문제 출처

백준 온라인 저지

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

2579번: 계단 오르기

 

문제 

 

입 / 출력

 

풀이

연속 세 개의 계단을 모두 밟지 않는 계단 오르는 최대 값을 구하기 위해서는

위의 그림처럼 현재 계단 값 + 이전 계단 값 + i - 3까지의 최대 값  혹은

위 그림처럼 현재 계단 값 + i - 2 까지의 최대 값 중 큰 값을 구하면

 

dp[n-1] 값이 총점수의 최댓값이 된다.

 

코드

#include <algorithm>
#include <iostream>

using namespace std;

const int MAX = 301;
int n, dp[MAX], stairs[MAX];

int main() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> stairs[i];
  }

  dp[0] = stairs[0];
  dp[1] = max(stairs[1], stairs[0] + stairs[1]);
  dp[2] = max(stairs[0] + stairs[2], stairs[1] + stairs[2]);
  for (int i = 3; i < n; i++) {
    dp[i] = max(dp[i - 2] + stairs[i], stairs[i - 1] + stairs[i] + dp[i - 3]);
  }
  cout << dp[n - 1] << "\n";
}