[BOJ / Python] 9465번: 스티커

문제: BOJ 9465번

입력: 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다. 연속하는 두 정수 사이에는 빈 칸이 하나 있다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력: 각 테스트 케이스 마다, 2n개의 스티커 중에서 두 변을 공유하지 않는 스티커 점수의 최댓값을 출력한다.

풀이

조건이 생각보다 까다로워서 오래 생각했던 문제이다. 하지만 간단히 대입해보면서 보면 풀이가 보였던 문제이다.

예시에 있는 값이다. 여기서 어떻게하면 문제를 풀 수있을까....??
오른쪽에 있는 (4,1), (4,2), (5,1), (5,2)를 보자. 스티커를 뜯을때 무조건 이 4개중에 하나를 뜯게된다.

만약 (4,1)을 고른다면, (5,2)가 세트이기 때문에 미리 업데이트를 해준다.
(4,2)의 경우도 똑같다.

이러면 초기값 세팅은 끝난다.

이떄부터는, 만약 (3,1)을 뜯는다면, (4,2)를 뜯거나 (5,2)를 뜯거나 두개의 경우가 있다. 각 색깔의 1번과 2번이 그 경우이다.
이 두개 중 더 큰 값을 더해서 (3,1), (3,2)를 업데이트해준다.
이러한 과정을 계속 거친다면?

첫번째 라인의 두개 중 더 큰 값이 이 문제의 답이다.ㅎㅎ

최종코드

import sys

input = sys.stdin.readline

n = int(input())
for _ in range(n):
    k = int(input())
    ar = []
    ar.append([0] + list(map(int, input().split())))
    ar.append([0] + list(map(int, input().split())))
    dp = [[0] * (k + 1) for _ in range(2)]

    dp[0][k] = ar[0][k]
    dp[1][k] = ar[1][k]
    dp[0][k - 1] = ar[0][k - 1] + dp[1][k]
    dp[1][k - 1] = ar[1][k - 1] + dp[0][k]
    for i in range(k - 2, 0, -1):
        for j in range(2):
            dp[j][i] += max(dp[(j + 1) % 2][i + 1], dp[(j + 1) % 2][i + 2]) + ar[j][i]
    print(max(dp[1][1], dp[0][1]))

편의를 위해 x열의 0번 인덱스는 안쓰고 1번부터 썼다.

초기값 설정이 좀 길다 ㅎㅎ
실버 1인데 체감상 전에 올린 안수빈수 (플레5)보다 훨씬 어렵다..............................