[백준] 스티커

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

9465번: 스티커

다이나믹 프로그래밍을 이용하는 문제입니다.

 

우선 문제부터 간단하게 요약하면, 

위 그림처럼 스티커와 점수가 있습니다. 이때, 한 스티커를 떼어내면 그 스티커의 바로 이웃한 스티커들은 사용할 수 없다고 할 때, 스티커를 최대한 높은 점수로 떼어낼 때의 점수를 구해야 합니다.

 

<Solution>

이 문제는 다이나믹프로그래밍을 이용해야 합니다. 

우선 스티커를 떼어내는 경우들을 생각해보면, 항상 지그재그 모양인 것을 알 수 있습니다. 무슨 이야기인지 그림으로 좀더 설명하면, 

스티커를 떼어내는 경우들은 무조건, 첫번째 그림처럼 완전한 지그재그의 형태이거나, 두번째 그림처럼 한칸 건너뛴 지그재그가 섞여 있는 그림입니다. 만약 세번째 그림처럼 지그재그가 아닌 형태로 떼어내려고 하면, 위에서 표시한 것 처럼 반드시 포함되어야 하는 칸을 빼먹은 것이므로 어쩔수 없이 다시 지그재그의 형태가 되는 것을 알 수 있습니다. 

 

이제 점화식을 세울 수 있습니다. 

 

두개의 dp array를 둡니다.

• dp1[i] = i번째 열에서 위의 element를 골랐을 때의 최댓값
• dp2[i] = i번째 열에서 아래의 element를 골랐을 때의 최댓값

이제 

        dp1[i] = i번째 윗쪽 element + max(dp2[i-1], dp2[i-2])
        dp2[i] = i번째 아랫쪽 element + max(dp1[i-1], dp1[i-2])

다음과 같은 점화식을 이용하면, 두개의 dp array의 결과를 얻을 수 있습니다. 이 점화식이 의미하는 바를 조금 더 구체적으로 설명하면, 

다음과 같이 설명할 수 있습니다.

 

실제 구현은 아래와 같습니다.

import sys

T = int(sys.stdin.readline().rstrip())

ans_list = [] 
for _ in range(T):
    n = int(sys.stdin.readline().rstrip())
    array = []
    for _ in range(2):
        array.append(list(map(int,sys.stdin.readline().rstrip().split())))
    dp1 = [0 for _ in range(n+1)]
    dp2 = [0 for _ in range(n+1)]

    dp1[1] = array[0][0]
    dp2[1] = array[1][0]

    for i in range(2,n+1):
        dp1[i] = array[0][i-1] + max(dp2[i-1], dp2[i-2])
        dp2[i] = array[1][i-1] + max(dp1[i-1], dp1[i-2])

    ans_list.append(max(dp1[n], dp2[n]))

for ans in ans_list:
    print(ans)