[DP] 1970번 건배

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

알고리즘

• Dynamic Programming
  • Top - Down (시간초과)
  • Bottom - Up (통과)

풀이

포인트

• 건배를 크로스해서 할 수 없음
  • $i$번째 사람과 $j$번째 사람이 건배를 했다면 그 두사람 기준으로 양 옆 사람들이 건배를 하는 가짓수로 문제를 나눌 수 있음
  • 이를 이용해 DP 점화식을 세울 수 있음

Dynamic Programming

DP 테이블을 아래와 같이 정의한다.

• $dp[i][j]$: $i$번째에서 $j$번째까지의 사람이 건배를 할 수 있는 최대 쌍의 개수

건배를 크로스해서 할 수 없으므로 아래와 같이 문제를 sub-problem으로 쪼갤 수 있다.

문제를 일반화하기 위해 $i$사람과 $j$번째 사람이 건배를 한 경우를 생각해보자 (빨간색 선). 이러한 상황에서는 건배를 크로스해서 할 수 없으므로 파란색 영역과 갈색 영역의 사람들이 건배를 할 수 있는 쌍의 개수를 구하는 문제로 쪼갤 수 있다.

PS 원형 문제는 종종 일직선 문제로 치환해서 생각하기도 한다. 이 문제도 그렇게 생각해보자.

$i$번째 사람부터 $j$번째 사람까지 건배를 할 수 있는 최대 쌍의 개수( = $dp[i][j]$)를 구하기 위해 아래의 그림을 생각해본다.

$i$번째 사람이 $k$번째 사람의 콜라 브랜드가 같아서 건배를 하는 경우, 문제는 색으로 표시한 두 sub-problem으로 나뉜다. sub-problem을 상세히 말하면 아래와 같다.

• $dp[i+1][k-1]$
• $dp[k+1][j]$

그런데 우리는 어떤 $k$과 $i$번째 사람이 건배를 해야할지 모른다. 따라서 모든 k번째 사람과 건배를 했다고 생각하고, 이 중 최대 쌍의 개수를 뽑는 사람을 택해야한다. 따라서 아래와 같은 점화식을 세울 수 있다.

• $dp[i][j] = max_k (dp[i+1][k-1] + dp[k+1][j] + 1)$

그런데 모든 $i$번째 사람과 $j$번째 사람 사이에 있는 모든 사람을 봤더니, 콜라 브랜드가 모두 달라서 건배를 하지 못할 수도 있다. 따라서 이 경우까지 고려해주면 최종 점화식은 아래와 같다.

• $dp[i][j] = max(dp[i+1][j], max_k (dp[i+1][k-1] + dp[k+1][j] + 1) )$

이를 구현할 때, TOP-DOWN 방식이 편할 것 같아서 아래와 같이 구현하였다.

[Source Code]

import sys
sys.setrecursionlimit(10**6)
n = int(input())
brand = list(map(int,input().split()))
dp = [[0]*(n+1) for _ in range(n+1)]
def go(i,j):
    if i >= j:
        return 0
    ans = dp[i][j]
    if ans != -1:
        return ans
    ans = go(i+1,j)
    for k in range(i+1,j+1):
        cur = 0
        if brand[i] == brand[k]:
            cur = go(i+1,k-1) + go(k+1,j) + 1
        if ans < cur:
            ans = cur
    dp[i][j] = ans
    return ans
print(go(0,n-1))

그런데 메모리 초과가 뜨는 것이다!!... 사용 메모리를 분석해보면, $n \leq 1000$이니까 dp 테이블에서 메모리를 많이 먹을 것이고, 2차원 테이블이므로 $1000 \times 1000 \times 4bytes \approx 3mb$인데... 아마도 recursion에서 memory을 많이 잡아먹는 것으로 예상된다. 추후에 python recursion memory 분석을 해봐야겠다는 생각과 함께... 다시 BOTTOM - UP 방식으로 구현하였다.
BOTTOM - UP 방식은 dp 테이블을 for 문을 이용해 채우는 방식이므로 사용 메모리를 쉽게 예측할 수 있다.

n = int(input())
brand = list(map(int,input().split()))
dp = [[0]*(n+1) for _ in range(n+1)]
for step in range(1,n):
    for i in range(n-step):
        cur = dp[i+1][i+step]
        for k in range(i+1,i+step+1):
            tmp = 0
            if brand[i] == brand[k]:
                # print(i + 1, k - 1, k + 1, i + step)
                tmp = dp[i+1][k-1] + dp[k+1][i+step] + 1

            if cur < tmp:
                cur = tmp
        dp[i][i+step] = cur
print(dp[0][n-1])

한 가지 주의할 점은 dp 테이블을 방식으로 채웠다는 점이다. 즉, 아래와 같은 순서로 채웠다.

1. $dp[1][2], dp[2][3], \cdots, dp[n-1][n]$
2. $dp[1][3], dp[2][4], \cdots, dp[n-2][n]$
3. $\cdots$
4. $dp[1][n]$

이는 점화식에서 sub-problem으로 쓰이는 문제의 참조 index를 참고하여 정하였다.

복잡도는 dp 테이블을 모두 채워야하고, 각 원소를 채울 때마다 $max_k$를 해야하므로 $O(10^3 \times 10^3 \times 10^3) = O(10^9)$라고 할 수 있겠다. python으로 제출했을 때는 시간초과가 뜨고 pypy는 통과했다.