9465. 스티커

 

https://www.acmicpc.net/problem/9465

9465번: 스티커

스티커를 때어내면, 그 스티커와 변을 공유하는 스티커들도 때어진다.

즉 때어낸 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커들은 사용할 수 없다.

이때 때어낼 수 있는 스티커 점수의 최대값을 구하는 문제.

 

일단 d[n]을 d[n] : 길이가 n인 스티커에서의 점수의 최댓값이라고 하자.

 

전의 포도주 문제와 비슷하게 n번째 열 일 때의 상태는 다음과 같이 있을 수 있다

0: 둘 다 떼어내지 않음

1 :위만 떼어냄

2 :아래만 떼어냄

(위 아래 둘 다 떼어내는 경우는 없다, 왜냐하면 스티커 하나를 떼어내면 인접 스티커도 떼어지기 때문)

 

n열이 0상태 일 때는(둘 다 떼어내지 않음),

n-1열은 0상태, 1상태, 2상태 모두 올 수 있다.

d[n][0] = max(d[n-1][0], d[n-1][1], d[n-1][2])

 

n열이 1상태 일 때는(위만 떼어냄),

n-1열이 0상태 또는 2상태가 있을수 있다.

d[n][1] = max(d[n-1][0], d[n-1][2]) + a[0][i-1]  // a[0][i-1]은 떼어낸 위 스티커

 

n열이 2상태 일 때는(아래만 떼어냄),

n-1열이 0상태 또는 1상태가 있을 수 있다.

d[n][2] = max(d[n-1][0], d[n-1][1]) + a[1][i-1]  // a[1][i-1]은 떼어낸 아래 스티커

 

 

d = [[0] * 3 for i in range(100002)]
a = [[0] * 100001 for i in range(2)]

t = int(input())
for x in range(t):
    n = int(input())
    a[0] = input().split()
    a[1] = input().split()

    for i in range(n):  # int형 변환
        a[0][i] = int(a[0][i])
        a[1][i] = int(a[1][i])

    d[0][0] = d[0][1] = d[0][2] = 0  # base

    for i in range(1, n+1):
        d[i][0] = max(d[i-1][0], d[i-1][1], d[i-1][2])  # 안 뗴어냄
        d[i][1] = max(d[i-1][0], d[i-1][2]) + a[0][i-1]  # 위 떼어냄
        d[i][2] = max(d[i-1][0], d[i-1][1]) + a[1][i-1]  # 아래 떼어냄

    for i in range(1, n+1):
        print(d[i][0], d[i][1], d[i][2])