[백준] #9465 Python

백준 9465번 파이썬
https://www.acmicpc.net/problem/9465

아이디어

점수의 합이 최대가 돼야 한다 -> 점수를 더 하는 방식이 두 가지로 나뉜다(끊김 없는 지그재그 방식의 점수 합산 & 끊김 있는 지그재그 방식의 점수 합산) -> 하나의 문제를 여러개로 쪼개서 해결할 수 있다(두 가지 방식 중 어떤 방식을 택할 것인지) -> DP로 풀자!

• range(1, n)을 돌 때 s가 1인 경우엔 s가 1일때의 값에 대각선 아래나 위의 값을 더해준다.
• s가 그 외의 값일 때, max(끊김 없는 지그재그 방식의 점수 합, 끊김 있는 지그재그 방식의 점수 합)을 현재의 노드에 더해주는 방식으로 dp값을 갱신한다.
• 마지막으로 0번째 행의 마지막 dp 값과 1번째 행의 마지막 dp값 중 더 큰 값을 출력해준다.

사실 처음에 풀 때는 dp라고는 생각을 못 하고 그리디로 풀려고 했다.
<틀린코드의 일부>

if stickers[row+1][column+1] + stickers[row][column+2] > stickers[row+1][column+2]:
    score += (stickers[row+1][column+1] + stickers[row][column+2])
    column += 2
else:
    column += 2
    score += stickers[row+1][column]
    row += 1

보이는 바와 같이 지속적으로 더해 온 합의 크기 비교가 아닌 순간순간의 큰 값 결정 방식으로 score에 큰 값을 더하면서 풀려고 했다.
따라서 score에 어떤 방식으로든 더해지면 column값 +2를 해줘서 다음 선택의 순간으로 넘어간다.

로직은 비슷하지만 현재까지 더해 온 값들을 비교하냐, 순간순간의 더 큰 값을 정답값에 더해주냐의 차이가 있었다.

전체코드

import sys
input = sys.stdin.readline
T = int(input())
for i in range(T):
    n = int(input())
    stickers = []
    for _ in range(2):
        stickers.append(list(map(int, input().split())))

    for s in range(1, n):
        if s == 1:
            stickers[0][s] += stickers[1][s-1]
            stickers[1][s] += stickers[0][s-1]
        else:
            stickers[0][s] += max(stickers[1][s-1], stickers[1][s-2])
            stickers[1][s] += max(stickers[0][s-1], stickers[0][s-2])

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