[BOJ]9465_스티커

📃 스티커

코드

t = int(input())

for i in range(t): #전체 테스트 횟수
    col = int(input())
    graph=[]
    for j in range(2): #row은 항상 2줄
        graph.append(list(map(int, input().split())))

    graph[0][1] += graph[1][0]
    graph[1][1] += graph[0][0]

    for k in range(2, col):
        graph[0][k] += max(graph[1][k-1], graph[1][k-2])
        graph[1][k] += max(graph[0][k-1], graph[0][k-2])

    print(max(graph[0][col-1], graph[1][col-1]))

풀이

n이 1일 경우, 스티커 2개가 인접해 있으므로 둘 중 높은 점수를 출력하면 된다.

n이 2일 경우 위와 같은 모양으로, 마지막 인덱스 1의 입장에서 봤을 때

빨간 체크를 더한 값 또는 파란 체크를 더한 값 중 높은 점수를 출력한다.

n이 3일 경우 위와 같은 모양으로, 마지막 인덱스 2의 입장에서 봤을 때

빨간 표시 두 개 중 하나를 더한 값 또는 파란 표시 두 개 중 하나를 더한 값 중 높은 점수를 출력한다.

이 때 인덱스 1에 있는 값은 n이 2일 경우의 과정을 한 상태의 값이 들어있다.

위와 같이 n이 2 이상일 경우 마지막 인덱스 n은

다른 줄의 인덱스 n-1 또는 n-2의 값 중 큰 값이 후보가 됨을 알 수 있다.