백준 2579 C++

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

2579번: 계단 오르기

정답 코드

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

int main() {
    int N, arr[300], stair[300], dp[300] = {0};
    cin >> N;
    for(int i=0 ; i<N ; i++){
        cin >> arr[i];
    }

    for(int i=0 ; i<N ; i++){
        stair[i] = arr[i];
    }

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

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

 

stair 배열 -  계단의 점수 저장

dp 배열 - 각 계단까지의 최대 누적 점수를 저장

 

dp[0] - 첫 번째 계단까지의 최대 누적 점수로 초기화

dp[1] - 두 번째 계단까지의 최대 누적 점수로 초기화

dp[2] - 세 번째 계단까지의 최대 누적 점수로 초기화

 

초기화 세 번을 하면 dp[3] ~ dp[N-1]을 계산해줄 차례!

 

점화식

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

 

dp[i] - i번째 계단까지의 최대 누적 점수는 max(dp[i-2] + stair[i], dp[i-3] + stair[i-1] + stair[i])

dp[i-2] + stair[i] - i번째 계단을 밟을 경우, 이전 계단(i-1번째 계단)은 밟지 않은 상태여야 함

dp[i-3] + stair[i-1] + stair[i] - i번째 계단을 밟을 경우, 이전 계단(i-2번째 계단)은 밟은 상태여야 하며, 그 이전 계단(i-3번째 계단)은 어떤 경우이든 상관 없음