[BOJ9465 - Python] 스티커

문제

---

9465번: 스티커

 

2행 n열로 배치되어 있는 스티커 뭉탱이가 있다.

 

 

스티커의 품질은 좋지 않아서, 스티커 한 장을 떼면 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다.

(뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 됨)

 

모든 스티커를 붙일 수 없으니, 각 스티커에 점수를 매겨 점수의 합이 최대가 되도록 스티커를 떼어내려고 한다.

즉, 2n개의 스티커 중 점수의 합이 최대가 되면서 서로 변을 공유하지 않는 스티커 집합을 구해야 한다.

 

 

(예시)

n = 2일 경우

 

50	10	100	20	40
30	50	70	10	60

 

100을 떼어냈을 때 10, 70, 20은 사용 불가가 된다.

 

50	10	100	20	40
30	50	70	10	60

 

풀이

---

점수가 큰 것부터 시작해서 경우의 수들을 보는 것으로 해결하려고 하면 머리가 bomb bomb 터져 죽게 된다.

이 문제는 DP로 접근한다면 해결할 수 있다.

 

 

스티커 행렬을 0번째 열부터 n-1번째 열까지 차례대로 볼 것이다.

 

이때 스티커를 떼었을 때 사용하지 못하는 스티커에 집중을 하는 것이 아닌,

현재 보고 있는 스티커를 떼어내려면 이전에 어떤 스티커를 떼었어야 했는지에 집중하는 것이다.

 

 

스티커를 하나 떼게 된다면 그 후에 사용할 수 없는 스티커는 해당 스티커의 왼쪽, 오른쪽, 위, 아래에 위치해있다.

다른 행에 영향을 주게 되기 때문에 0번째 행과 1번째 행을 구분하여 생각할 필요가 있다.

 

아래 그림에서 O의 위치에 있는 스티커를 떼어내려면 1 또는 2번 위치의 스티커를 떼었어야 한다.

 

		O
1	2

 

1	2
		O

 

 

O의 열 인덱스를 i라고 하면,

 

0번 행, i번 열([0][i])에 위치한 스티커를 떼기 위해서는 [1][i-2]와 [1][i-1]에 위치하는 스티커를 떼어야 하는데,

점수의 합이 최대가 되어야 하므로 [1][i-2]와 [1][i-1] 중 더 큰 값이 저장되어 있는 쪽을 선택해야 한다.

 

1번 행, i번 열([1][i])에 위치한 스티커에 대한 것도 동일하다.

[0][i-2]와 [0][i-1] 중 더 큰 값이 저장되어 있는 쪽을 선택해야 한다.

 

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

 

전체 코드를 보면 더 와닿을 것이다.

 

코드

---

import sys

T = int(sys.stdin.readline().strip())

result = []
for _ in range(T):
    n = int(sys.stdin.readline().strip())

    sticker = []
    for i in range(2):
        sticker.append(list(map(int, sys.stdin.readline().split())))

    if n > 1:
        sticker[1][1] += sticker[0][0]
        sticker[0][1] += sticker[1][0]

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

    result.append(max(sticker[0][n - 1], sticker[1][n - 1]))

for r in result:
    print(r)