[알고리즘][백준] 9465번 스티커 - 파이썬(python) 풀이

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

9465번: 스티커

---

대각선끼리 더하는거보다 한번 건너 뛰어서 더하는게 더 커질때를 어떻게 해야할까 고민하게 되었다 

아직 dp가 알듯말듯.... 

import sys

t = int(sys.stdin.readline())

for _ in range(t):
    n = int(sys.stdin.readline())
    sticker = []

    # 스티커 2*n
    for _ in range(2):
        sticker.append(list(map(int, sys.stdin.readline().split())))

    # 2*1의 경우
    if n == 1:
        print(*max(sticker))

    # n > 1인 경우
    else:
        # 1,2열의 대각선 합
        sticker[1][1] += sticker[0][0]
        sticker[0][1] += sticker[1][0]

        # 대각선 합 vs i-2의 값중 하나
        for i in range(2, n):
            sticker[0][i] += max(sticker[1][i-1], sticker[1][i-2])
            sticker[1][i] += max(sticker[0][i-1], sticker[0][i-2])

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

9465_스티커.py

0.00MB