[BOJ] 9465 / 스티커 / Python

[BOJ] 9465 / 스티커 / Python

[BOJ] 9465 / 스티커 / Python

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

9465번: 스티커

풀이

주어진 데이터와 조건을 분석하여, 규칙을 찾으면 쉽게 풀리는 문제였다.

 

하지만 익숙한대로 손이 간다고, DFS 를 이용한 완전 탐색으로 구현해 보았다.

import copy


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

def deleteStiker(i, j, stickers):
    stickers[i][j] = 0
    if i:
        stickers[i-1][j] = 0
    else:
        stickers[i+1][j] = 0
    if j < len(stickers[0]) - 1:
        stickers[i][j+1] = 0
    if j > 0:
        stickers[i][j-1] = 0
    return stickers
    
def DFS(i, j, stickers, res):
    global answer
    if sum(stickers[0]) == 0 and sum(stickers[1]) == 0:
        answer = max(answer, res)
        return
    
    for i in range(2):
        for j in range(N):
            if stickers[i][j]:
                tmp = stickers[i][j]
                stikersCopy = deleteStiker(i, j, copy.deepcopy(stickers))
                DFS(i, j, stikersCopy, res+tmp)
            
    
for _ in range(T):
    N = int(sys.stdin.readline())
    stickers = []
    answer = 0
    for _ in range(2):
        stickers.append(list(map(int, sys.stdin.readline().split())))
    
    for i in range(2):
        for j in range(N):
            stickersCopy = deleteStiker(i, j, copy.deepcopy(stickers))
            DFS(i, j, stickersCopy, stickers[i][j])
    print(answer)

결과는, 너무나도 당연하게 시간초과!

 

문제를 풀기 위해서는 정답의 규칙을 찾아야 하였다.

 

(0, 3) 의 스티커를 선택하기 위한 방법은,

O	X	O
X	O

X	X	O
O	X

두가지 방법이 있는데, 이 중 선택된 스티커 점수의 합이 큰 경우만 찾으면 된다.

 

	0	1	2	3	4
0	50	10	100	20	40
1	30	50	70	10	60

주어진 예제 1의 경우로 확인하자면

	0	1	2	3	4
0	50	10 + 30[1,1] = 40	100 + max( 100[1,1] , 30[1,0]) = 200	20 + max( 110 [1,2] , 100 [1,1]) = 130	40 + max( 210 [1,3] , 110 [1,2]) = 250
1	30	50 + 50[0,1] = 100	70 + max( 40[0,1] , 50[0,0]) = 110	10 + max( 200[0,2] , 40[0,1]) =210	60 + max( 130 [1,3] , 200 [1,2]) = 260

result = max( 250[0,4] , 260 [1,4] ) = 260

 

위에서 찾은 규칙을 코드로 작성하면 다음과 같다.

import sys

T = int(sys.stdin.readline())
    
for _ in range(T):
    N = int(sys.stdin.readline())
    stickers = []
    answer = 0
    for _ in range(2):
        stickers.append(list(map(int, sys.stdin.readline().split())))
    
    stickers[0][1] += stickers[1][0]
    stickers[1][1] += stickers[0][0]
    
    for i in range(2, N):
        stickers[0][i] += max(stickers[1][i-2], stickers[1][i-1])
        stickers[1][i] += max(stickers[0][i-2], stickers[0][i-1])
    print(max(stickers[0][N-1], stickers[1][N-1]))

 

---

참고 블로그

https://pacific-ocean.tistory.com/197

[백준] 9465번(python 파이썬)