[ 백준 9465번 스티커 ] Python 코드 (DP)

1. 문제

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

9465번: 스티커

---

2. 아이디어

다이나믹 프로그래밍의 핵심은 DP배열이 가지는 의미 & DP배열을 계산하는 방법이다.

2.1. DP배열이 가지는 의미

지금까지 풀어본 문제들을 보면,  DP[n]은 대부분 다음 두 가지 중 하나의 의미를 가졌다.

1. n번째를 선택했을 때의 최적값
2. n번째까지 고려했을 때의 최적값 (n번째를 선택하지 않는 경우까지 고려)

 

이 문제는 첫번째 경우에 해당한다.

왜냐하면 총 N열의 스티커가 주어졌을 때, 최댓값을 구하는데 마지막 N열을 선택하지 않을 수는 없다.

N-1번째 어떤 선택을 했더라도 항상 마지막 N열에서 하나를 더 고를 수 있기 때문에, 최댓값은 항상 마지막 N열에서 스티커를 고르는 경우를 한정된다.

그러면 우리가 원하는 답도 DP배열의 마지막에 위치하게 된다.

주의할 점: N번째 열이란 마지막 열을 말하는 것이다. 중간의 어떤 n열에 대해서는 선택을 하지 않을 수도 있다.

 

그런데 한 가지 특이한 점이 있다.

보통 문제들은 DP[n]에 대한 선택값이 하나로 주어진다.

그런데 이 문제는 n열에서 2개의 선택지가 있다. 

그래서 DP 배열을 2개의 행으로 만들어서 풀어야 한다. 의미는 여전히 똑같다.

DP[i][n] == n열에서 i행 스티커를 마지막으로 골랐을 때의 최대가치

자연스럽게 문제의 답은 DP[0][-1]과 DP[1][-1]중의 최댓값이다.

2.2. DP배열의 계산 방법

임의의 n에 대해,  DP[0][n]을 계산해보자.

기본적으로 DP[0][n] = max( Case1, Case2, ... ) + sticker[0][n] 의 형태를 가진다.

sticker[0][n]가 마지막에 더해지는 이유는 DP[i][n] 의미상 당연하다. (n열에서 i행의 스티커를 마지막으로 골랐을 때의 최대가치)

우리가 주의해야할 부분은 Case들을 모두 빠짐없이 생각해내는 것이다.

 

Case 1. DP[1][n-1]

가장 쉽게 떠오르는 Case이다.

마지막으로 대각선에 위치한 sticker[1][n-1]을 고른 경우이다.

 

Case2. DP[1][n-2]

n-1열에서 아무것도 안 고르고, n-2열에서 n열로 바로 넘어오면서 최댓값을 만들 수 있을지 직관적으로 생각하기 어렵다.

이런 경우 반례를 최대한 생각해봐야한다.

아래 그림과 같이 sticker[1][n-2] + sticker[0][n]가 sticker[0][n-2] + sticker[1][n-1] + sticker[0][n]보다 큰 경우, 오히려 n-1을 건너뛰는 것이 최댓값을 만들 수 있다.

 

아래 두개는 Case로 둬야할지 헷갈리지만, 결과적으로 고려할 필요 없는 Case들이다.

 

Case3? DP[0][n-2]

DP[0][n-2]에 sticker[0][n]을 더한 경우는 결코 최댓값이 될 수 없다.

sticker[1][n-1]를 무조건 더 선택할 수 있기 때문이다. 그리고 그 경우는 Case1에서 DP[1][n-1]에 포함되어 있다.

 

Case4? DP[i][n-3]

n-1을 건너 뛰고 최댓값이 나올 수 있다면, n-1과 n-2를 연속으로 건너뛰고도 최댓값이 나올 수 있을가 의심해볼만 하다.

하지만 그림으로 그려보면 불가능하다는 것을 바로 알 수 있다.

아래 그림처럼 n-1과 n-2를 동시에 건너 뛴 경우, 무조건 sticker[1][n-1]를 추가 선택할 수 있기 때문에 최댓값이 될 수 없다.

그리고 이 경우 역시 Case1의 DP[1][n-1]에 포함되어 있다.

이러한 이유로 n-3열 이하를 마지막으로 선택했던 경우는 고려할 필요 없다.

 

위의 경우는 DP[0][n]에 대한 설명이었고, DP[1][n]도 동일한 아이디어로 계산하면 된다.

---

3. 코드

스티커 길이가 1이거나 2일 경우 위의 아이디어를 적용하면 IndexError가 나므로, 이 부분만 추가 처리 해주었다.

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(2)]

    # 2행 DP배열 형성
    DP = [[0] * N for _ in range(2)]

    # 스티커 길이가 1일 경우
    DP[0][0] = arr[0][0]
    DP[1][0] = arr[1][0]
    if N == 1:
        print(max(DP[0][0], DP[1][0]))
        continue

    # 스티커 길이가 2일 경우
    DP[0][1] = arr[1][0] + arr[0][1]
    DP[1][1] = arr[0][0] + arr[1][1]
    if N == 2:
        print(max(DP[0][1], DP[1][1]))
        continue

    # 스티커 길이가 3이상일 경우
    for i in range(2, N):
        # 메인 아이디어
        DP[0][i] = max(DP[1][i - 2], DP[1][i - 1]) + arr[0][i]
        DP[1][i] = max(DP[0][i - 2], DP[0][i - 1]) + arr[1][i]

    print(max(DP[0][-1], DP[1][-1]))