몽상실현개발주의

[BOJ] 9465 / 스티커 / Python 본문

Algorithm PS/BOJ

[BOJ] 9465 / 스티커 / Python

migrationArc 2021. 5. 12. 10:17

[BOJ] 9465 / 스티커 / Python

[BOJ] 9465 / 스티커 / Python

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

 

9465번: 스티커

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의

www.acmicpc.net

풀이

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

 

하지만 익숙한대로 손이 간다고, 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 파이썬)

문제 링크: https://www.acmicpc.net/problem/9465 9465번: 스티커 문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를

pacific-ocean.tistory.com

 

Comments