[BOJ 9465] 스티커(C++)

스티커 (Silver 2)

문제

전체 문제 보기

9465번: 스티커

접근법

이 문제는 동적 계획법으로 풀 수 있습니다. 우선 점화식을 세워보겠습니다. 임의의 위치 n에서 우리는 두 가지 선택을 할 수 있습니다. 위쪽 스티커를 선택하거나, 아래쪽 스티커를 선택할 수 있습니다. (아무것도 선택하지 않을 필요는 없습니다.)

아래쪽 스티커 선택

만약 아래쪽 스티커를 선택하게 되면 바로 직전 위치에서는 위쪽 스티커를 선택할 수 있습니다.

하지만 아래의 그림처럼 직전 위치의 스티커를 포기하고 두 칸 전 위치의 위쪽 스티커를 선택하는 것이 더 이득일 수 있습니다. 그래서 우리는 직전 스티커와 두 칸 전 위치의 스티커까지 확인해야 합니다.

위쪽 스티커 선택

위쪽 스티커를 선택하는 경우도 마찬가지 입니다. 아래의 그림처럼 n번 위치에서 위쪽 스티커를 선택할 경우 직전에는 아래쪽 스티커를 선택할 수 있습니다.

그리고 앞서 언급한바와 같이 아래의 그림처럼 두 칸 전 위치의 스티커까지도 확인해야 합니다.

나머지 그 이전 경우에는 모두 탐색되었기 때문에 더 이상 볼 필요는 없습니다.

점화식

따라서 점화식은 다음과 같습니다. \(f(m,n)\)은 n 위치에서 m에(0: 아래쪽, 1: 위쪽) 스티커를 선택한 경우 가치의 최댓값을 의미합니다.

\[f(0,n) = max(f(1,n-1), f(1,n-2)) + value(0,n)\]

\[f(1,n) = max(f(0,n-1), f(0,n-2)) + value(1,n)\]

그리고 우리는 n번째 아래쪽 혹은 위쪽을 선택한  경우중 큰 값을 정답으로 취할 수 있습니다. 따라서 정답은 다음과 같습니다.

\[\mbox{answer} = max(f(0,n), f(1,n))\]

전체 구현

위 점화식을 다음과 같이 바텀업 방식으로 구현하였습니다.

#include <iostream>
#include <array>
#include <algorithm>

#define endl '\n'
using namespace std;

const int MAX_L = 100'001;
void solve()
{
    int n;
    cin >> n;
    array<array<int, MAX_L>, 2> value{};

    // cache[0][i]: i번째 스티커 위쪽을 뗀 경우
    // cache[1][i]: i번째 스티커 아랫쪽을 뗀 경우
    array<array<int, MAX_L>, 2> cache{};

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

    cache[0][1] = value[0][1];
    cache[1][1] = value[1][1];

    for (int i = 2; i <= n; ++i)
    {
        cache[0][i] = max(cache[1][i - 1], cache[1][i-2]) + value[0][i];
        cache[1][i] = max(cache[0][i - 1], cache[0][i-2]) + value[1][i];
    }

    cout << max( cache[0][n], cache[1][n]) << endl;
}

int main() {
    // 입출력 성능 향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    int T;
    cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}