[파이썬] 백준 9465 : 스티커 (실버1)

[파이썬] 백준 9465 : 스티커 (실버1)

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

---

풀이

방향성 생각

• 상태를 나누는 기준은 줄 선택 / 이전에 스티커를 선택했는지 -> 2*2로 총 4가지이다.
• 이전에 스티커를 선택한 경우 : 스티커를 선택하지 않은 경우 2가지 + 스티커를 선택한 경우 (반대 줄에서)
• 이전에 스티커를 선택하지 않은 경우 : 스티커를 선택하지 않은 경우 2가지 + 스티커를 선택한 경우 2가지

---

전체코드

import sys
input = lambda : sys.stdin.readline().rstrip()

def dp(N,arr):

    V = [[[0]*N for _ in range(2)] for _ in range(2)]
    V[1][1][0] = arr[1][0]
    V[1][0][0] = arr[0][0]

    for i in range(N-1):
        for j in range(2):
            V[1][j][i+1] = max(V[0][0][i],V[0][1][i],V[1][j^1][i]) + arr[j][i+1]
            V[0][j][i+1] = max(V[0][0][i],V[0][1][i],V[1][0][i],V[1][1][i])

    return max(V[i][j][-1] for i in range(2) for j in range(2))

for _ in range(int(input())):
    N = int(input()) 
    arr = [list(map(int,input().split())) for _ in range(2)]
    print(dp(N,arr))

코멘트

• .