1. 개요
문제 링크: https://www.acmicpc.net/problem/11066
2. 코드
import sys
t = int(sys.stdin.readline().rstrip())
for i in range(0, t):
k = int(input())
dp = []
sum = [0]
# arr initialize (0-indexed)
arr = list(map(int, input().split()))
# sum initialize (1-indexed)
sum.append(arr[0])
for j in range(2, len(arr) + 1):
sum.append(sum[j-1] + arr[j-1])
# DP process (1-indexed)
dp = [[0] * (k+1) for _ in range(k + 1)]
# 1) adjacent elements initialize
for m in range(1, k):
dp[m][m+1] = arr[m-1] + arr[m]
# 2) Build DP table loop
for m in range(3, k+1): # 몇 칸을 동시에 볼 것인가? (3인 경우는 ["2 3 4" 5], [2 "3 4 5"] 두 경우를 보게 된다]
for n in range(1, k - m + 2): # 어디를 시작점으로 할 것인가? (1인 경우는 ["2" 3 4 5], 2인 경우는 [2 "3" 4 5])
min_val = 50000000
for l in range(1, m): # 칸막이 offset (1인 경우는 [2 | 3 4 5], 2인 경우는 [2 3 | 4 5])
min_val = min(min_val, dp[n][n + l - 1] + dp[n + l][n + m - 1] + sum[n+m-1] - sum[n-1])
dp[n][n + m - 1] = min_val
print(dp[1][k])3. 풀이 메모
1. 단계
선택지가 1개만 있을 때 -> 선택지가 2개만 있을 때 -> ... -> 선택지가 k개만 있을 때
2. 상태
선택지가 1개만 있을 때: (자기 자신 페이지)
선택지가 2개만 있을 때: 칸막이가 두 수 사이 - [2 | 3]
선택지가 3개만 있을 때: 칸막이가 세 수 사이 - [2 | 3 1] , [2 3 | 1]
....3. 결정 변수
각 단계에서 칸막이를 어디에 두는가?
결국 동적계획법 + 분할 정복이다. 하지만 이 풀이에서 정말 주의해야할 점은 DP 테이블에 저장되는 내용은 '그 상태에서 저장되는 부분 합의 최저' 라는 점이다. 여기서 선택지가 1개인 상태에 대해서는 그 유일한 1개의 값을 DP에 저장해야 하는 것처럼 보이나 실상은 그렇지 않다는 점이다.
DP에 저장되는 값들은 i~j까지 부분 합 조합 중 최소인 값이다. 즉, 합을 하는 것이 이미 내재되어 있다는 뜻이고, 부분 합을 진행할 부분 집합의 원소가 1개밖에 없는 경우는 부분 합을 진행할 수가 없다. 따라서 DP[i][i]는 항상 0이 저장되어야 한다.
분할 정복과 이분 탐색과는 다르게 이런 메모이제이션에서는 이러한 접근 방식을 취한다는 것을 아는 것이 중요한 것 같다.
한편, 이 문제는 거시적으로 봤을 때는 최적 부분 구조를 만족하지 않는 것처럼 보인다. 다시 말해, 중간 과정에서 어떤 부분 합 조합을 선택하냐 따라서 최종 정답에 도달되는 과정이 달라지니, 이 문제를 general하게 해결하는 근사한 하나의 알고리즘이 없는 것처럼 보인다. 하지만 이를 해결하는 방법은 모든 부분 합을 따지면서 DP 테이블을 완성 시키는 것으로 보완할 수 있다. 어느정도 Brute-force한 부분을 포함시켜도 전체 연산량이 DP 덕분에 어느 정도 줄어들었으므로 문제가 해결되는 것으로 보인다. Brute-force라지만, 각 과정에서 하는 것은 고작 더하기 연산 두번 아닌가.
4. 코멘트
더 찾아보니 Knuth Algorithm이라는 현 O(n^3)의 알고리즘을 O(n^2)으로 줄일 수 있는 알고리즘이 있는 것 같다. 하지만 지금은 특정 문제를 해결할 수 있는 알고리즘을 공부하기 보다는 좀 더 포괄적인 문제를 해결할 수 있는 알고리즘을 공부하는데 주력하고 싶다.
