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

1. 개요

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

9465번: 스티커

1-1. 설명

상근이 여동생 상냥이는 문반구에서 스티커 2n개를 구매했다. 스티커는 2행 n열로 배치되어 있다. 이를 이용해 책상을 꾸미려고 하나, 스티커의 품질은 좋지않다. 한장을 떼면 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수 합이 최대가 되게 스티커를 떼내려고 한다. 최대 점수를 구하는 프로그램을 작성한다. 

1-2. 제한 사항

 - 첫 줄에 테스트 케이스 개수 T가 주어짐

 - 각 케이스 첫줄에 n이 주어지며, n은 1 이상 100,000 이하

 - 다음 두줄에 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커 점수

 - 점수는 0 이상 100 이하 정수

---

2. 구현

2-1. 풀이

DP임을 알았으나, 점화식을 어떤식으로 짜야할 지 제대로 감이 잡히지 않아 풀이를 간단하게 찾아보았다. 어차피 상하좌우 변은 사용 못하므로, 무조건 대각선으로 점수를 합해야 한다는 풀이를 보고 점화식을 짜보았다. 

스티커 점수

위의 스티커표를 보고 예시를 들어보자. 만약 3열까지 점수를 합산해야 한다면, 50 + 50 + 100 하나의 경우의 수와, 30 + 100 하나의 경우의 수 총 두가지가 나오게 될 것이다. 이 중 큰 수를 dp에 저장하면 된다.

두 경우의 수

여기서, 2열에서는 앞의 저장된 수가 1개이므로 0열에 0을 대입해주어야 점화식이 완성된다. 또 주의할 점은 30 + 100에서는 30만 더해주면 되나, 50 + 50 + 100 부분에서 이미 50 + 50 은 앞선 dp에서 저장이 되어있는 상태이므로, 실제로 점화식으로 풀면 100 + 100이 된다. 

최종 점화식

이를 코드로 구현하면 완성된다. 막상 점화식을 만들고 나면 그리 어렵지 않으나, 생각하기까지 아직 시간이 걸리는 듯 했다. DP를 조금 더 연습해봐야겠다. 

2-2. 코드 

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

constexpr size_t MAX_NUM = 100001;
int stickers[2][MAX_NUM];
int dp[2][MAX_NUM];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int T, n;
    cin >> T;
    for (int tc = 0; tc < T; tc++) {
        cin >> n;
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < n; j++) {
                cin >> stickers[i][j];
            }
        }
        dp[0][1] = stickers[0][0];
        dp[1][1] = stickers[1][0];
        for (int i = 2; i <= n; i++) {
            dp[0][i] = max(dp[1][i - 1], dp[1][i - 2]) + stickers[0][i - 1];
            dp[1][i] = max(dp[0][i - 1], dp[0][i - 2]) + stickers[1][i - 1];
        }
        cout << max(dp[0][n], dp[1][n]) << "\n";
    }
    
    return 0;
}