[백준] 스티커 9465 (python)

문제 링크

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

나의 풀이

• 우선, 3xn 크기의 dp테이블과 2xn 크기의 stickers배열을 생성합니다.
• dp[0][n] stickers[0][n]의 스티커를 뜯었을 때의 최댓값을 저장하고, 두 번째 행도 이와 마찬가지입니다.
• dp[2][n]은 stickers[0][n], stickers[1][n] 모두 뜯지 않았을 때의 최댓값을 저장합니다.

 

스티커를 뜯는 방식으로 3가지를 고려할 수 있습니다.

1. 0행의 n열 스티커를 뜯는 경우 -> stickers[0][n]을 뜯는 경우 
   • stickers[0][n]을 뜯은 경우 이와 인접한 stickers[0][n-1] 스티커는 뜯을 수 없기 때문에, stickers[0][n-1] 스티커를 뜯지 않은 경우인 dp[1][n-1], dp[2][n-1] 값 중 최댓값과 stickers[0][n]의 값을 더한 결과가 최댓값이 됩니다.
   • 이를 점화식으로 표현하면 아래와 같이 나오게 됩니다.
   • dp[0][n] = max(dp[1][n-1], dp[2][n-1]) + stickers[0][n]
2. 1행의 n열 스티커를 뜯는 경우
   • 위 1번의 경우와 마찬가지로 stickers[1][n]을 뜯게 되면 stickers[1][n-1]은 뜯을 수 없기 때문에 아래와 같이 점화식이 나오게 됩니다.
   • dp[1][n] = max(dp[0][n-1], dp[2][n-1]) + stickers[0][n]
3. n열의 스티커를 모두 뜯지 않는 경우
   • 이 경우는 stickers[0][n-1], stickers[1][n-1]모두 뜯을 수 있기 때문에, dp[2][n]은 dp[0][n-1], dp[1][n-1]중 최댓값이 됩니다. 이때 n열의 스티커는 뜯지 않는 것에 주의해야 합니다.
   • dp[2][n] = max(dp[0][n-1], dp[1][n-1])

Code

# 스티커
# https://www.acmicpc.net/problem/9465

import sys
input = sys.stdin.readline

test_cases = int(input())

for _ in range(test_cases):
    stickers_num = int(input())
    stickers = [list(map(int, input().split())) for _ in range(2)]

    dp = [[0] * stickers_num for _ in range(3)]
    dp[0][0] = stickers[0][0]
    dp[1][0] = stickers[1][0]

    for n in range(1,stickers_num):
        # 0행의 i번 째 스티커 뜯은 경우
        dp[0][n] = max(dp[1][n-1], dp[2][n-1]) + stickers[0][n]

        # 1행의 i번 째 스티커 뜯은 경우
        dp[1][n] = max(dp[0][n - 1], dp[2][n - 1]) + stickers[1][n]

        # i번 째 열의 스티커를 뜯지 않은 경우
        dp[2][n] = max(dp[0][n-1], dp[1][n-1])

    answer = max(dp[0][-1], dp[1][-1])
    answer = max(answer, dp[2][-1])
    print(answer)

Git

https://github.com/youngh0/Algorithm/blob/master/dp/boj_9465.py