[Python | 9465] 스티커

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

---

문제 설명

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

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

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

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

 

📌 시간 제한: 1초

---

입력

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

---

출력

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

---

문제 접근

2행 N열로 구성된 스티커 판이 있습니다. 각 칸에는 점수가 적혀 있으며, 이 점수는 해당 스티커를 선택했을 때 얻을 수 있는 값이다. 
하지만 단순히 점수가 높은 스티커만 골라서는 안 된다. 이유는 한 스티커를 선택하면 그 상하좌우로 인접한 스티커를 사용할 수 없게 되기 때문이다. 이러한 조건을 보며 처음에는 각 열마다 위와 아래 중 더 큰 점수를 단순히 선택하면 되지 않을까 하는 직관적인 생각이 들 수 있다.

 

왜 단순히 큰 값을 고르면 안 될까?

예를 들어, 아래와 같은 스티커 배열이 있다고 가정해 볼 때:

[50, 10, 100, 20, 40]
[30, 50, 70, 10, 60]

 

매 열에서 위와 아래 중 큰 점수만 고른다고 가정하면,

1열: 50, 2열: 50, 3열: 100, 4열: 20, 5열: 60 → 총합 280점이 된다.

 

하지만 여기서 생각해야 할 점은, 이렇게 선택한 값들이 실제로 함께 선택 가능한 조합인지 여부다. 위 예시에서 1열 위쪽(50)을 선택하면 2열 아래쪽(50)은 인접한 스티커이기 때문에 선택할 수 없다. 즉, 단순한 최댓값 선택은 이후 선택지에 제약을 만들어 최종 점수는 예상보다 낮아질 수 있다.

이처럼 이 문제는 각 선택이 이후 선택에 영향을 주는 구조이며, 특히 같은 행 또는 인접한 열에 있는 스티커 선택 여부가 다음 단계의 선택 가능성과 연결되어 있다.

 

이 문제는 결국, 이전의 선택이 다음 선택을 제한하므로 매 순간 "현재 최적"을 선택하더라도 전체 최적해가 보장되지 않는다. 따라서 문제를 풀기 위해서는 현재까지의 최적 선택 결과를 기억하면서, 다음 선택을 할 때 그 결과를 토대로 누적 점수를 계산해야 한다. 즉, 이 문제는 동적 프로그래밍(DP) 방식으로 해결하는 것이 적합하다. 그리고 이때 중요한 점은, 단순히 열(index)만 상태로 관리하는 것이 아니라, 이전 열에서 위칸을 골랐는지 아랫칸을 골랐는지도 함께 고려해야 한다는 점이다. 즉, DP는 `dp[행][i]` 형태의 2차원 배열로 구성해야 한다.

 

💡 문제 풀이 아이디어

2행 n열의 스티커 배열에서, 우리는 인접하지 않도록 스티커를 선택하면서 최대 점수를 누적해야 한다.
즉, i번째 열의 윗칸 또는 아랫칸을 선택할 때, 그 이전 열에서 상대편 행의 스티커를 골랐는지 여부가 중요하다.

따라서, 다음과 같이 DP 테이블을 설계한다:

• dp[0][i]: i열까지 고려했을 때, i열의 윗칸을 선택했을 때의 최대 점수
• dp[1][i]: i열까지 고려했을 때, i열의 아랫칸을 선택했을 때의 최대 점수

여기서 중요한 점은, 같은 열에서 위·아래 둘 다 고를 수 없고, 이전 열에서 같은 행을 연속으로 고르는 것도 안 된다는 점이다. 즉, dp[0][i]는 dp[1][i-1] 또는 dp[1][i-2]에서만 올 수 있고, 반대로 dp[1][i]는 dp[0][i-1] 또는 dp[0][i-2]에서 올 수 있다.

 

✅ 점화식

dp[0][i] = sticker[0][i] + max(dp[1][i-1], dp[1][i-2])
dp[1][i] = sticker[1][i] + max(dp[0][i-1], dp[0][i-2])

• i열의 윗칸을 고르면: 그 전 열 혹은 전전 열의 아랫칸 값 중 최대 + 현재 값
• i열의 아랫칸을 고르면: 반대로 윗칸 기준으로 동일한 점화식 적용

즉, 초기 조건

• n == 1일 경우: 위/아래 중 큰 값 선택
• n >= 2일 경우:

dp[0][0] = sticker[0][0]
dp[1][0] = sticker[1][0]
dp[0][1] = sticker[0][1] + dp[1][0]
dp[1][1] = sticker[1][1] + dp[0][0]

---

구현

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    n = int(input())
    sticker = [list(map(int, input().split())) for _ in range(2)]

    if n == 1:
        print(max(sticker[0][0], sticker[1][0]))
        continue

    dp = [[0]*n for _ in range(2)]
    dp[0][0] = sticker[0][0]
    dp[1][0] = sticker[1][0]
    dp[0][1] = sticker[0][1] + dp[1][0]
    dp[1][1] = sticker[1][1] + dp[0][0]

    for i in range(2, n):
        dp[0][i] = sticker[0][i] + max(dp[1][i-1], dp[1][i-2])
        dp[1][i] = sticker[1][i] + max(dp[0][i-1], dp[0][i-2])

    print(max(dp[0][n-1], dp[1][n-1]))

 

그리고 이 문제는 공간 최적화도 가능하다.

지금은 dp[0][i], dp[1][i]를 전부 저장해서 O(n) 크기의 배열을 사용하고 있지만, 실제로는 매번 i-1, i-2까지만 참조한다.

그래서 전체 배열을 만들 필요 없이, 슬라이딩 윈도우 방식으로 최근 3칸만 유지해도 점화식을 구현할 수 있다. 즉, 기존 O(n) 공간을 O(1) 공간으로 줄일 수 있다.

dp = [[0]*3 for _ in range(2)]
    dp[0][0] = sticker[0][0]
    dp[1][0] = sticker[1][0]
    dp[0][1] = sticker[0][1] + dp[1][0]
    dp[1][1] = sticker[1][1] + dp[0][0]