(2579) 계단 오르기

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

단계별로 풀어보기

21단계(동적 계획법 1) 8번째

 

 

 

dp[k]: k번째 계단을 올랐을 때 최대 점수

이때 k번째 계단을 오르려면 k-1번째 계단에서 올라오거나 k-2번째 계단에서 올라와야 한다

1) k-1번째 계단에서 오르는 경우: k-2번째 계단은 밟을 수 없다(연속으로 3개를 밟게 되므로). 따라서 k-3번째 계단에서 올라와야 하고 이때 값은 dp[k-3]+v[k-1]+v[k]

2) k-2번째 계단에서 오르는 경우: dp[k-2]+v[k]

둘 중 큰 값을 저장하면 된다.

 

 

 

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

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