백준 2579번 <계단 오르기> - C++

Dynamic Programming 유형 마스터 프로젝트 까진 아니고 어느정도 궤도에 올리기 나만의 프로젝트를 진행중인데.. 하 진짜 쉽지가 않다. 고등학교 다닐 때도 점화식 문제 진짜 못풀어서 싫어했는데, 얘는 무조건 점화식을 찾아야만 풀 수 있는 문제 유형이란 말이다!!!!!

번외로 요즘 내가 새기고 다니는 말이 있다. "Intellectual Honesty"라는 단어다. 직역하면 지적인 정직성인데, 진실을 추구하고, 실수로 부터 배워서 공유하자는 의미다. 그래서 예전과는 다르게, 고민의 시간을 늘리는 방향으로 공부를 진행 중이다. 근데 이번 문제는.. 점화식과 초기세팅을 어떻게 해야 할 지 도저히 감이 안 잡혀서 슬쩍.. 참고해버렸다.

 

아무튼 보자 내가 지금 밟아야 되는 계단이 N번째 계단이다

• N-1번째 계단을 밟을 수 있다. 단, N-2번째는 밟으면 안 된다.(3연속)그러므로 N-3번째 계단도 반드시 밟아야 한다.
  • N-3번째 까지 계단의 최댓값과, N-1번째는 반드시 밟아야 하므로 계단에 적힌 숫자를 더해준다
• N-2번째 계단도 밟을 수 있다. 애는 N-3번째를 밟는 지 안 밟는 지 모르므로, N-2번째 계단까지의 최댓값이다.

이 두 경우의 최대값을 산출해서 현재 계단에 적힌 숫자와 더해줘야 하므로, 이렇게 점화식이 완성된다.

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

 

초깃값은 어떻게 세팅해야 할까

dp[1] = stair[1]. 자명하다

dp[2] = stair[1] + stair[2]. 이것 역시 자명하다. 한 칸 띄어서 출발 - 2번째 할 수도 있지만, dp[2]에는 2번째까지의 최댓값이 들어가야 하므로 반드시 1번 계단도 밟아야 한다.

dp[3] = stair[3] + max(stair[1], stair[2])이제부터 연속을 세어야 하므로, 두 계단 중 큰 값을 더해주어야 한다.

 

전체 코드는 아래와 같다.

#include <algorithm>
#include <iostream>
#include <math.h>
#include <string>
#include <vector>
using namespace std;

int main() {
  
  int stair[301] = {0};
  int dp[301] = {0};
  int n;
  cin >> n;

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

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

  
  for (int i = 4; i <= n; i++) {
    dp[i] = stair[i] + max(stair[i - 1] + dp[i - 3], dp[i - 2]);
  }

  cout << dp[n];

  return 0;
}