[BOJ/백준] 11066 파일 합치기

import sys
input = sys.stdin.readline

T = int(input())

def divide_two(ind_X,ind_Y):
    if ind_X == ind_Y:
        return books[ind_X]
    cache_data = dp[ind_X][ind_Y]
    if cache_data != -1:
        return cache_data

    temp = float('inf')
    mid_sum = prefix_sum[ind_Y+1] - prefix_sum[ind_X]
    for k in range(ind_X,ind_Y):
        temp = min(temp,divide_two(ind_X,k)+divide_two(k+1,ind_Y)+mid_sum)
    dp[ind_X][ind_Y] = temp
    return temp

    

for _ in range(T):

    N = int(input())
    dp = [[-1]*N for _ in range(N)]
    books = list(map(int,input().split()))
    prefix_sum = [0]*(N+1)
    for i in range(1,N+1):
        prefix_sum[i] = prefix_sum[i-1] + books[i-1]
    result = float('inf')

    for i in range(N-1):
        result = min(result,divide_two(0,i)+divide_two(i+1,N-1))

    print(result)

어렵게 푼 문제이다.

 

먼저 특정 범위의 합을 구해야하기 때문에, prefix_sum을 먼저 구해준다.

 

그리고 재귀를 통해, 특정 위치로 나누었을때의 최소값을 구하는 함수를 통해 구해준다.

 

만약 0~N-1 칸이 있다고 했을때, 0~i 와 i+1~N-1을 나눠서 소분해서 구해주면 된다.

 

전체 0~N-1칸을 생각해보지 말고, 

 

작은 공간 A ~ A+2 칸이 있다고 해보자,

A   | |   A+1   | |   A+2

30  | |   40     | |    50 

 

라고 하면

 

1번 경우 : 30 // 40 + 50

 

2번 경우 : 30 + 40 // 50

 

각각을 구해보면

 

1번 경우 : 90 + 90 + 30 = 90 + 120 = 210

2번 경우 : 70 + 70 + 50 = 70 + 120 = 190

 

그러면 A~A+2칸에서 가장 적게 구하는 것은 30+40 // 50 일때이다.

 

그리고 위의 경우를 봐보면 120은 30 + 40 + 50을 다 더한거와 같고, 그 앞의 값만 바뀐다는 것을 알 수 있다.

 

이걸 식으로 표현하면 divide_two(A,ind) + divide_two(ind+1,B) + (books[A] + books[A+1] + books[A+2]) 

 

가 된다.

 

결국 정리하면 divide_two라는 함수에 들어왔을때 ind_X 와 ind_Y가 같으면 books[ind_X]의 값을 반환해주면 되고,

 

그 외의 경우에는 ind_X와 ind_Y의 사이값으로 나뉘었을때를 가정하고, 재귀를 통해 최소값을 구해주면 된다.

 

또한 이렇게 구한 값들은 변하지 않기 때문에

 

dp에 저장을 해주면 된다. dp[ind_X][ind_Y] 는 ind_X에서 ind_Y 까지의 범위를 계싼했을때 최저 값인 것이다.

 

위와 같이 구하면 파일 합치기의 최소값을 구할 수 있다.

 

하지만 이 방법은 N^3을 돌기 때문에 시간이 오래걸린다.

 

그래서 다른 사람들의 풀이를 보고 찾은 방법은 다음과 같다.

 

 

# # Knuth's Optimization
# # https://wogud6792.tistory.com/20

import sys
input = sys.stdin.readline

T = int(input())

for _ in range(T):
    N = int(input())
    books = list(map(int,input().split()))
    prefix_sum = [0]*(N+1)
    INF = float('inf')
    dp =[[INF] *N for _ in range(N)]
    min_k_store_array = [[0]*N for _ in range(N)]
    for i in range(N):
        dp[i][i] = 0
        min_k_store_array[i][i] = i
        prefix_sum[i+1] = prefix_sum[i] + books[i]
    for term in range(1,N):
        for i in range(N-term):
            j = term+i
            for k in range(min_k_store_array[i][j-1],min_k_store_array[i+1][j]+1):
                if k<N-1 and dp[i][j] > dp[i][k]+dp[k+1][j]+ prefix_sum[j+1] - prefix_sum[i]:
                    dp[i][j] = dp[i][k]+dp[k+1][j] + prefix_sum[j+1] - prefix_sum[i]
                    min_k_store_array[i][j] = k
    print(dp[0][N-1])

 https://wogud6792.tistory.com/20

 

위의 블로그에 설명이 잘 되어 있으니 참조 바란다.

 

DP에서 특정한 조건을 만족할 경우, 최적활 할 수 있는 기법이다.

 

위의 최적화 기법의 점화식을 보고 구현한 것이다.

 

최적화 기법이므로, 실행속도가 확연히 줄어든다.

 

하지만 저는 실전에서는 쓰기 힘들것 같다. 쓸려면 이 Knuth Optimization에 대해서 더 공부해야할 것 같다.