[백준] 9465 - 스티커

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

9465번: 스티커

DP 유형의 '스티커' 문제이다.

데이터가 추가되면서 옛날에 맞았던 코드가 틀리자 다시 풀어보게 되었다.

 

기본적인 DP의 문제풀이 방식은 문제를 단계별로 쪼개어

이전단계에 푼 문제를 이번 단계 풀이에 활용하는 것이다.

 

이 문제는 이전 단계에 어떻게 문제를 풀었는지에 따라

이번 단계에 문제 풀이 방식이 달라진다는 점이 특징인 문제였다.

 

피보나치 수열, 정수삼각형과 같은 단순 메모이제이션 방식만 활용하는 문제를 풀다가

이 문제를 처음 만났을 때는 엄청 당황했던 기억이 난다.

---

풀이 아이디어

---

이 문제의 풀이 핵심은, 이전 단계에 문제를 푼 방식에 따라 나누어 저장한다는 것이다.

문제 예제 입력을 보자.

 

50 10 100 20 40

30 50 70 10 60

 

우선 기본적으로, i번째 세로줄까지의 최적을 구하기 위해

i-1번째 세로줄까지의 최적해에, i번째 추가할 스티커를 선택해야한다.

그런데 i번째에 추가할 수 있는 스티커가 i-1번째에 어떤 스티커를 선택했느냐에 따라 갈린다.

 

i-1번째에 윗줄의 스티커를 선택했다면, i번째에는 아랫줄의 스티커만 선택할 수 있고,

i-1번째에 아랫줄의 스티커를 선택했다면, i번째에는 윗줄의 스티커만 선택할 수 있다.

 

이렇게 경우에 따라서 제약이 나뉘는 경우에는 각 경우별로 모두 저장을 해주면 된다.

이 문제같은 경우에는

 

i-1번째에 윗줄의 스티커를 선택한 경우의 최적 해

i-1번째에 아랫줄의 스티커를 선택한 경우의 최적 해

 

두 가지를 모두 저장해두고, 저장한 값을 바탕으로

i 번째에 대해서도 저렇게 2가지 경우를 모두 저장한다.

그러면 아래와 같은 점화식을 쓸 수 있다.

 

i번째에 위의 스티커를 선택한 경우 최적해 = i-1번째에 아래의 스티커를 선택한 경우 최적해 + i번째 위의 스티커

i번째에 아래의 스티커를 선택한 경우 최적해 = i-1번째에 위의 스티커를 선택한 경우 최적해 + i번째 아래의 스티커

 

그런데 문제 예시가 참 잘 나온 것이 이렇게만 구하면 답을 구할 수가 없다.

당연히 스티커 점수의 최대를 구하려면 가능한 많은 스티커를 선택해야하니,

i번째에 스티커를 선택해야지만 최적이 될 것 같다.

그러나 위 문제 예시의 경우 4번째 줄의 스티커는 선택하지 않는 것이 최적이다.

 

그래서 한가지를 더 구해야 한다.

'i 번째에 스티커를 선택하지 않은 경우 최적해' 이다.

i-1 번째에 스티커를 선택하지 않았다면 i번째에는 위, 아래 스티커를 모두 선택할 수 있다.

따라서 위 점화식은 아래와 같이 바뀐다.

 

i번째에 위의 스티커를 선택한 경우 최적해

= max( i-1번째에 아래의 스티커를 선택한 경우, 스티커를 고르지 않은 경우) + i번째 스티커

 

i번째에 아래의 스티커를 선택한 경우 최적해

= max( i-1번째에 위의 스티커를 선택한 경우, 스티커를 고르지 않은 경우) + i번째 스티커

 

i번째에 스티커를 선택하지 않은 경우 최적해

= max( i-1번째에 위의 스티커를 선택한 경우, 아래의 스티커를 선택한 경우, 스티커를 고르지 않은 경우)

 

i번째에 스티커를 고르지 않는 경우, 제약이 없기 때문에, i-1번째의 모든 경우를 비교해서 최적해를 가져다 쓰면 된다.

정답을 출력할 때는 가장 마지막 줄의 3가지 경우에서 최적해를 출력하면 된다.

---

소스 코드

---

import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
    n = int(input())
    table = [[0 for _ in range(n)] for _ in range(3)]
    top_line = list(map(int, input().split()))
    bottom_line = list(map(int, input().split()))
    table[0][0] = top_line[0]
    table[1][0] = bottom_line[0]

    for i in range(1, n):
        table[0][i] = max(table[1][i-1], table[2][i-1]) + top_line[i]
        table[1][i] = max(table[0][i-1], table[2][i-1]) + bottom_line[i]
        table[2][i] = max(table[0][i-1], table[1][i-1], table[2][i-1])

    print(max(table[0][-1], table[1][-1], table[2][-1]))

3행의 DP 테이블을 사용하였는데,

1행은 윗줄의 스티커를 선택한 경우의 최적해,

2행은 아랫줄의 스티커를 선택한 경우 최적해

3행은 스티커를 선택하지 않은 경우 최적해

이렇게 나누어서 저장하도록 했다.