[C++] BOJ_2579 계단 오르기

문제: 백준 2579 (c++)

풀이과정

이 문제는 조건이 조금 까다롭다고 느낄 수 있다.

계단이 네 개가 있다고 가정을 했을 때, 계단 1, 2는 무조건 한 칸씩 가는 것이 최댓값을 구할 때 도움이 된다.

따라서 dp 배열에 먼저 값을 지정해 주었고,

세 번째 계단은 애초에 문제 조건에 연속 세 계단을 밟을 수 없다고 되어 있기에

한 칸, 두 칸 또는 두 칸, 한 칸으로 계단을 밟아야 한다.

---

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

int main(){

    int dp[301] ;
    int a[301] ;
    int n ;
    int cnt = 0 ;

    cin >> n ;

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

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

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

따라서 이렇게 max 함수를 이용하여 세 번째 계단을 지정해 주었다.

그 후의 계단부터는 Bottom-up 방식을 이용하여 풀어주었다.

---

코드를 보면 알 수 있듯이 두 가지 경우를 나누어 max 함수를 이용해 최댓값을 구할 수 있도록 해주었다.

주의할 점은 무조건 dp 배열을 더하는 것이 아닌 원래 계단의 점수를 입력받았던 배열을 더해야 한다는 것이다.