BOJ. 2579

#BOJ2579

계단 오르기

계단 오르기 문제를 보면 규칙을 단계별로 나눠 놓았는데 DP 생각이 났다. 이전에도 설명했다시피 디피는 기본적으로 문제를 쪼개서 아주 간단한 문제로 생각하는 것이다. 재귀와 매우 유사한데 이 문제같은 경우에는 2칸짜리 계단까지는 그냥 간단하게 생각할 수 있지만 3칸에 가는 순간 1 -> 3으로 갈 지 2 -> 3으로 갈지 선택지가 생기게 된다. 이 두 개를 비교해서 3칸째를 구해주고 난 후 4칸째부터 두 가지 케이스 중 하나를 고민해 주면 문제를 비교적 쉽게 해결해줄 수 있다. 오늘 디피가 조금 잘 되는 것 같으니 디피 문제를 쭉 모아서 풀어봐야 겠다.

#include <iostream>
using namespace std;

int main(){
   ios::sync_with_stdio(false);
   cin.tie(NULL);
   cout.tie(NULL);
   int n;
   cin >> n;
   int* arr = new int[n];
   for (int i = 0; i < n; i++){
       cin >> arr[i];
   }
   int* ans = new int[n];
   ans[0] = arr[0];
   ans[1] = ans[0] + arr[1];
   ans[2] = max(arr[0] + arr[2], arr[1] + arr[2]);
   for (int i = 3; i < n; i++){
       ans[i] = max(ans[i - 2] + arr[i], ans[i - 3] + arr[i-1] + arr[i]);
   }
   cout << ans[n - 1];
}