[BOJ] 9465 스티커 (Python / 파이썬)

🧷 문제

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

각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내는 문제이다. (단, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.)

🛠 풀이

이 문제 또한 혼자 풀다가 해결하지 못해 다른 사람들의 풀이를 참고했다.
여러 사람들의 풀이를 보는데도 이해가 힘들었는데, 거의 다 같은 풀이여서 조금 더 생각을 해봐야할 것 같다.
이 중 내가 이해한 코드의 풀이는 두 가지다.

1.

Step 1.
 스티커의 점수 리스트를 입력받은 후에, 위쪽 스티커를 뗀 경우(up), 아래쪽 스티커를 뗀 경우(down), 아무것도 떼지 않은 경우(non) 세 가지로 나누어 값을 구해간다.

Step 2.
 for문을 돌면서 위쪽 스티커를 뗀 경우에는 max(이전에 아래 스티커를 뗀 경우, 아무것도 떼지 않은 경우),
아래쪽 스티커를 뗀 경우에는 max(이전에 위쪽 스티커를 뗀 경우, 아무것도 떼지 않은 경우),
아무것도 떼지 않은 경우에는 max(이전에 위쪽 스티커를 뗀 경우, 이전에 아래 스티커를 뗀 경우)로 나누어 구한다.

for i in range(n):
    up, down, non = max(down, non) + stickers[0][i], max(up, non) + stickers[1][i], max(up, down)    

Step 3.
 이렇게 for문을 n번 모두 돌게 되면 그 중 가장 큰 값이 우리가 구하는 값임을 알 수 있다.

2.

Step 1.
 점화식을 찾기가 힘들었는데, i번째 인덱스의 DP table (dp[0][i], dp[1][i])은 같은 행, i-1번째 인덱스의 값을 그대로 갖거나 대각선에 위치한 i-1번째 인덱스의 값에 해당 stickers점수를 더해준 값을 비교해 더 큰 값을 갖는다.

Step 2.
 즉, 점화식은 dp[0][i] = max(dp[0][i-1], dp[1][i-1] + stickers[0][i]), dp[1][i] = max(dp[1][i-1], dp[0][i-1] + stickers[1][i]) 이다.

느낀점

채점을 해본 후에 메모리 사용량과 걸린 시간을 비교해보면 첫번째 방법이 모든 측면에서 효율적인 것을 볼 수 있었다.
다이나믹 프로그래밍은 적절한 점화식을 빠르게 찾는 것이 중요한 것 같다.
이 문제는 Solved.ac 기준 실버 2의 난이도인데, 이렇게 고생한 건 더 많이 풀어보면서 보완해야 할 점인 것 같다.

🖊 나의 코드

######1.######
import sys
 
if __name__ == "__main__":
    t = int(input())
 
    for _ in range(t):
        n = int(input())
        dp = [[0] * n for _ in range(2)]
        stickers = []
        for _ in range(2):
            stickers.append(list(map(int, input().split())))
 
        up, down, none = 0, 0, 0
 
        for i in range(n):
            up, down, none = max(down, none) + stickers[0][i], max(up, none) + stickers[1][i], max(up, down)    
 
        print(max(up, down, none))
 
######2.######
import sys
 
if __name__ == "__main__":
    t = int(input())
 
    for _ in range(t):
        n = int(input())
        dp = [[0] * n for _ in range(2)]
        stickers = []
        for _ in range(2):
            stickers.append(list(map(int, input().split())))
 
        dp[0][0], dp[1][0] = stickers[0][0], stickers[1][0]
 
        for i in range(1, n):
            dp[0][i] += max(dp[0][i-1], dp[1][i-1] + stickers[0][i])
            dp[1][i] += max(dp[1][i-1], dp[0][i-1] + stickers[1][i])
 
        print(max(dp[0][n-1], dp[1][n-1]))