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

🥈 Silver 3

✏️ 1차 솔루션

DP 로 풀이

1. 첫번째 계단은 무조건 자기 자신의 값만 가짐
2. 2번째 계단부터는 1계단 아래 값과 2계단 아래 값을 비교해서 더 큰 값을 자기 자신의 값과 더해서 저장
   ➡️ 1계단 아래 값을 더할 경우에는 flag++ 하고 flag 값이 2보다 크면 연속 3계단이 되기 때문에 flag 가 2 미만인 경우에 한해 1계단을 올라가도록 하기
   ➡️ 2계단 아래 값을 더할 때는 flag 값을 초기화
3. n-1 번째 계단의 최종 값이 1계단 이전 값과 n-1 계단 값을 더한 것이라면 마지막 계단을 밟을 경우, 연속 3계단이 되기 때문에 이 경우에는 n 번째 계단의 값은 n-2 계단의 최대값에 n 번째 계단 값을 더한 것이 되어야 함.
   but n-1 번째 계단 이전에 n-2 계단을 밟지 않았다면 n-1 번째 계단, n-2 번째 계단을 밟는 경우 중에 최대값을 n 번째 계단 값과 더해서 최종 결과 도출

🚨 1차 trouble

처참히 실패,,
bottom-up 방식의 시도는 좋았으나 최대값 경로를 찾을 수 있는 방안인지는 알 수 없음
마지막 계단을 꼭 밟아야 한다는 점을 어떻게 제한을 두고 구현하는지가 관건인 것 같음

✏️ 최종 솔루션

각 계단의 최대값은 그 계단을 반드시 밟는다는 전제 하에 최대값을 산출해야 함
자기 자신이 최대값이 되는 1번 계단, 1번 계단을 밟는 것이 최대값인 2번 계단을 제외하고 3번 계단부터는 해당 계단을 밟는 경우를 2가지로 나눌 수 있음

1. n-2 번 계단을 밟고 n 번 계단을 밟는 경우
2. n-3 번, n-1 번 계단을 밟고 n 번 계단을 밟는 경우

이 2가지 경우에만 연속 3계단 밟는 것을 피할 수 있음

❗️ 2번 방법의 경우, n-3 번 계단 최대값 + n-1 번 계단 최대값 이 아닌 n-3 번 계단 최대값 + n-1 번 계단 값 으로 계산해야 함
➡️ n-3 번 계단을 밟고 n-1 번을 밟으면 연속 계단이 아니기 때문에 n-3 번 계단 이전에 어떤 계단을 밟았던 상관없으므로 n-3 번은 최대값을 취하지만, n-1 번 계단의 경우, n-1 번 계단을 밟는 최대값 산출 경로를 따라오는 것이 아니라 무조건 n-3 번 계단을 밟고 n-1 번을 밟는 순서이기 때문에 최대값이 아닌 계단 값을 더해줘야 함

📌 self feedback

최대값을 정하는 방법이 잘못되었음
n-1, n-2 최대값 중에 n 의 최대 값을 정하는 것이 아니라 일단 n 을 무조건 밟는다면 이전에 어떤 계단을 밟을 수 있는지 한정하고 그 중에 최대값을 선택하는 방법으로 했어야 함
연속 계단을 처리하는 것도 헷갈렸는데 2계단 전에 어떤 계단을 밟는지 한정한다면 연속 3계단을 방지할 수 있었음

✏️ 최종 code

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    int stair[301];
    int dp[301];

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

    dp[1]=stair[1];
    dp[2]=stair[1]+stair[2];

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

    cout << dp[n];
}