[백준 파이썬] 9465 스티커

 

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

9465번: 스티커

문제

 

---

 

아이디어

가장 많은 스티커를 선택하기 위해서는 지그재그형식으로 스티커를 뽑을 때 가장 많이 뽑게된다.

하지만 모든 스티커를 반드시 지그재그로 뽑았을 시 최대값이 되는것이 아니므로 다음 스티커를 뽑을 때 2가지 경우의수가 생긴다.

1. 똑같이 지그재그로 뽑을경우.

 

2. 한 스티커를 건너뛰고 다른 행의 스티커를 뽑을경우

 

해당 경우의 수들을 dp로 계산하면 되겠다고 생각했다.

 

---

풀이

if n > 1:
        dp[0][1] += dp[1][0]
        dp[1][1] += dp[0][0]

가장 먼저 n이 1이 아닐경우(스티커가 2행 이상)를 계산했다.

각 2번째 열의 스티커의 경우 이전 대각선 스티커값의 합과 같으므로 위와같이 계산하였다.

 

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

이후 계산은 위와같다.

각 스티커의 dp값은 건너뛰지않았을 경우, 건너뛸경우 중 큰 값을 선택하면 된다.

---

코드

T = int(input())

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

    if n > 1:
        dp[0][1] += dp[1][0]
        dp[1][1] += dp[0][0]

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

    print(max(dp[0][n-1], dp[1][n-1]))