[백준] 2579번 계단 오르기

문제

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

풀이과정

DP[i] 를 i번째 계단을 밟을 경우 최대로 얻을 수 있는 점수라고 한다.

3번째 계단일 경우에는 2, 3번째 계단을 밟을 경우와 1, 3번째 계단을 밟을 경우를 비교하여 큰 값을 저장한다.

4번째 이후로는 현재 계단만 밟을 경우와 현재, 이전 계단을 밟을 경우를 비교하여 큰 값을 저장한다.

소스코드

#include <iostream>
#include <algorithm>
 
using namespace std;
int DP[301], stair[301];
 
int main()
{
    int n;
 
    cin >> n;
 
    for (int i = 1; i <= n; i++)
    {
        cin >> stair[i];
    }
 
    for (int i = 1; i <= n; i++)
    {
        if (i != 3) DP[i] = DP[i - 1] + stair[i];
        else // 3번째 계단일 경우
            DP[i] = max(DP[i - 2] + stair[i], stair[i-1] + stair[i]);
 
        if (i >= 4) // 4번째 이상 계단일 경우
            DP[i] = max(stair[i] + DP[i - 2], stair[i] + stair[i - 1] + DP[i - 3]); // 현재 계단만 밟을 경우와 현재,이전 계단 밟을 경우 비교
 
    }
 
    cout << DP[n];
 
    return 0;
}