[BOJ] 9465. 스티커

Python3,DP

문제

입출력

입출력 예시

주요 포인트

양옆에 닿아 있는 숫자는 더할 수 없고, 대각선의 숫자만을 더할 수 있다.
표로 정리하면

인덱스 1은 각각 대각선인 숫자를 더한다. 이후에는 대각선 누적합(k-1)과 k-2값 중 큰 수를 선택해서 더한다.

최종 코드

t = int(input())

for i in range(t):
    s = []
    n = int(input())
    
    for j in range(2):
        s.append(list(map(int, input().split())))
    
    for k in range(1, n):
        if k == 1:
            s[0][k] += s[1][k-1]
            s[1][k] += s[0][k-1]
        else:
            s[0][k] += max(s[1][k-1], s[1][k-2])
            s[1][k] += max(s[0][k-1], s[0][k-2])

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

피드백

for문 안에서 2줄의 점수를 입력받고, 계산을 하는 거였다.
너무 어렵게 생각해서 어떻게 점수를 뽑아야 할지 감이 안 섰다.
맞닿아 있는 변이 안 된다는 것은 대각선이 가능하단 거였다.
저번 문제에서 봤던 1일 때 처리도 있는 문제였다.