[백준] 9465번: 스티커 - Python

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

9465번: 스티커

아이디어

dp를 이용해서 풀면 될거라고 바로 보임

왼쪽의 스티커부터 선택해 나가 dp배열을 채워나가보자

예제에서 보자

왠쪽부터 dp 배열을 만들어 간다고 하면 첫줄은 50과 30이 그대로 들어간다.

이제 두번째 줄은 대각으로 더한 값이 가장 큰 코스트가 되는 경우니 둘을 더한 값을 dp에 저장한다.

이렇게 셋팅이 됐다면 점화식이 들어가면 된다.

(0,2) 좌표의 스티커가 선택되는 경우는

• (1,1)을 선택 후 (0,2) 선택
• (1,0)을 선택 후 (0,2) 선택

이 두가지 경우만 존재한다.

 

이를 점화식으로 표현하면 dp(0,i) ( i>=2 )는  dp(1, i-1)과 dp(1, i-2) 중에 더 큰걸 가져와 (0,i) 스티커 코스트와 더해 저장하면 된다.

 

이를 코드로 구현해보자

구현

import sys

input = sys.stdin.readline

case = int(input())
result = []
for i in range(case):
    n = int(input())
    sticker = [list(map(int, input().split())) for _ in range(2)]

    if n == 1:
        result.append(max(sticker)[0])

    else:
        dp = [[0]*n for _ in range(2)]

        dp[0][0], dp[1][0] = sticker[0][0], sticker[1][0]
        dp[0][1], dp[1][1] = dp[1][0] + sticker[0][1], dp[0][0] + sticker[1][1]

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

        result.append(max(max(dp[0]), max(dp[1])))

for i in result:
    print(i)

처음 틀린 이유는 n이 1일 경우를 빼먹고 해서 틀렸었다... ㅎ

 

마무리

• dp쉽게 풀리니까 은근 재밌네..? 
• 코딩 조아