greentea31's Note

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

풀이 과정

각각의 계단에는 점수가 적혀있고, 계단 1칸 건너기, 1칸 건너뛰고 건너기 두 개의 선택이 가능할 때 세 칸 연속으로 계단을 건너지 않고 마지막 계단을 밟을 때의 가능한 최대 점수 값을 구하는 문제이다.

각 계단을 올랐을 때 가능한 최대 점수 값을 기록해가면서 DP로 해결할 수 있다.

i번째 계단에서의 가능한 점수 최댓값 D[i], i번째 계단을 건널 때의 점수 값 A[i]에서

D[i] = max(D[i-2], D[i-3] + A[i-1]) + A[i]가 성립한다.

i-2번째 계단에서 2칸 건너오거나, i-1번째 계단에서 1칸 건너오거나 해야 하는데 i-1번째 계단에서 건너오는 경우는 i-2번째 계단을 밟지 않았다는 것을 점화식에 반영해 주어야 하기 때문에 D[i] = D[i-3] + A[i-1] + A[i]의 식이 된다.

DP는 언제나 초기 값 설정에 유의해주어야 한다. D[2]는 A[0] + A[2], A[1] + A[2] 둘 중 큰 수로 지정해주자.

소스 코드

#include <iostream>
using namespace std;

int D[301];
int A[301];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int stair, num;
    cin >> stair;

    for (int i = 0 ; i < stair; i++) {
        cin >> num;
        A[i] = num;
    }

    D[0] = A[0];
    D[1] = D[0] + A[1];
    D[2] = max(D[0] + A[2], A[1] + A[2]);

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

    cout << D[stair-1] << '\n';

    return 0;
}