코딩테스트 대비/BOJ

[Baekjoon/Python] 9465번: 스티커 - 효과는 굉장했다!

bluetag_boy 2022. 4. 3. 18:25
반응형
 

9465번: 스티커

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의

www.acmicpc.net

 

알고리즘 분류

  • 다이나믹 프로그래밍

 

 

SOLUTION

import sys

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

for _ in range(T):
    N = int(sys.stdin.readline())
    sticker = [list(map(int, sys.stdin.readline().split())) for _ in range(2)]

    # 위에서 때는 경우, 아래서 때는 경우를 나눠서 구한다
    for i in range(1, N): 
        # i가 1일때는 왼쪽 대각선에 붙어 있는 스티커는 때지지 않으므로 점수에 더한다
        if i == 1:
            sticker[0][i] += sticker[1][i-1]
            sticker[1][i] += sticker[0][i-1]

        else:
            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]))