[BOJ/C++] 계단 오르기(2579번)

1. 개요

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

2579번: 계단 오르기

1-1. 설명 

계단 오르기 게임은 계단 아래 시작점부터 꼭대기에 위치한 도착점까지 가는 게임이다 각각 계단에는 일정한 점수가 쓰여있는데 그 계단을 밟으면 점수를 얻게 된다. 계단 오를때의 규칙을 참고하여 점수의 최댓값을 도출해내는 프로그램을 작성한다.

1-2. 제한 사항

 - 첫째 줄에 계단의 개수가 주어짐

 - 둘째 줄부터 한줄씩 제일 아래에 놓인 계단부터 순서대로 각 계단의 쓰여있는 점수가 주어짐

 - 계단 개수는 300개 이하이며, 점수는 10,000이하의 자연수

---

2. 구현

2-1. 풀이

DP의 Bottom-up 방식을 사용하였다. 첫번째 점화식은 한눈에 알았지만, 두번째 점화식은 도출해내는 시간이 조금 걸렸다. 다른 문제를 통해 더 연습해야 할 것 같다. 

2-2. 코드

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

int dp[300];
int score[300];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, count = 1;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> score[i];

    dp[1] = score[1];
    dp[2] = score[1] + score[2];
    for (int i = 3; i <= n; i++) {
        dp[i] = max(score[i] + dp[i - 2], score[i] + score[i - 1] + dp[i - 3]);
        // 1. 한번에 2칸
        // 2. 한칸씩 연달아 밟을 때
    }
    
    cout << dp[n] << "\n";

    return 0;
}