문제#

문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.

상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.

모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오. 즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유 하지 않는 스티커 집합을 구해야 한다.

위의 그림의 경우에 점수가 50, 50, 100, 60인 스티커를 고르면, 점수는 260이 되고 이 것이 최대 점수이다. 가장 높은 점수를 가지는 두 스티커 (100과 70)은 변을 공유하기 때문에, 동시에 뗄 수 없다.

입력#

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다. 연속하는 두 정수 사이에는 빈 칸이 하나 있다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력#

각 테스트 케이스 마다, 2n개의 스티커 중에서 두 변을 공유하지 않는 스티커 점수의 최댓값을 출력한다.

풀이 과정#

처음에 문제를 봤을때는 상하좌우의 스티커를 못쓴다고 하길래 백트래킹 알고리즘인가 싶었지만 2행 n열인것과 입력 제한을 봤을때 $O(N)$까지만 허용되어 보여 동적계획법을 사용해야할 것 같아 보였습니다.

처음에 점화식은 아래와 같이 구성했습니다.

• i번쨰에 위쪽을 선택한 경우: 선택지 중 최대 + 위쪽 선택 값
  • i-1 번째에 아래와 i-2번째의 위쪽 최선의 해를 선택한 경우
  • i-2 번째의 아래 쪽 최선의 해를 선택한 경우
• i번째에 아래쪽을 선택한 경우: 선택지 중 최대 + 아래쪽 선택 값
  • i-1 번째에 위쪽과 i-2번째의 아래쪽 최선의 해를 선택한 경우
  • i-2 번째의 위 쪽 최선의 해를 선택한 경우

이러한 4가지 경우의 수로 풀려했지만 계속 틀렸습니다.

한 1시간 고민한 결과 도무지 답이 나오지 않아 챗봇에게 점화식 힌트를 주라고 물어봤더니 선택하지 않는 경우의 수 상태도 포함하라고 조언을 받아 코드를 다시 작성했습니다.

새로운 점화식은 다음과 같습니다.

• i번째에 선택하지 않는 경우: 선택지 중 최대
  • i-1번째 선택하지않는 최선의 해 경우
  • i-1번째 위쪽 선택한 최선의 해 경우
  • i-1번째 아래쪽 선택한 최선의 해 경우
• i번째에 위쪽 선택한 경우: 선택지 중 최대 + 위쪽 선택 값
  • i-1번째 선택하지않는 최선의 해 경우
  • i-1번째 아래쪽 선택한 최선의 해 경우
• i번째에 아래쪽 선택한 경우: 선택지 중 최대 + 아래쪽 선택 값
  • i-1번째 선택하지않는 최선의 해 경우
  • i-1번째 위쪽 선택한 최선의 해 경우

이렇게 코드를 다시 작성한 결과 맞았습니다.

추가적으로 여기서 느낀 점은 내가 문제의 상태를 정의하고 점화식으로 바꾸는 것에 약하다고 느꼈고 DP문제를 더 많이 풀어봐야겠습니다.

코드#

#include <iostream>

using namespace std;

int N, T;

int upper[100'000];
int downer[100'000];

int dp[100'000][3];

int main()
{
    cin >> T;
    for (int t = 0; t < T; ++t)
    {
        cin >> N;
        for (int i = 0; i < N; ++i) cin >> upper[i];
        for (int i = 0; i < N; ++i) cin >> downer[i];

        if (N == 1)
        {
            cout << max(upper[0], downer[0]) << "\n";
            continue;
        }
        dp[0][1] = upper[0];
        dp[0][2] = downer[0];
        for (int i = 1; i < N; ++i)
        {
            dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][1], dp[i - 1][2]));
            dp[i][1] = upper[i] + max(dp[i - 1][0], dp[i - 1][2]);
            dp[i][2] = downer[i] + max(dp[i - 1][0], dp[i - 1][1]);
        }
        cout << max(max(dp[N - 1][0], dp[N - 1][1]), dp[N - 1][2]) << "\n";
    }
}