백준 11066 풀이 (파일 합치기, DP, Knuth Optimization)

문제 이해가 어렵지는 않다. 양 옆으로만 더할 수 있고 이에 대한 비용을 계산하여 최종 비용이 가장 낮은 경우의 값을 구하는 것이다. 만약 재귀로 푼다면 말도 안되는 연산을 해야하기 때문에 DP로 풀어야 한다.

처음에 갈피를 못잡다가 이미지를 검색해 보니 묶어서 DP로 푸는걸 알게 되었다. 

단 각 묶음안에서의 조합이 최소화 이어야 한다. 그래야 DP를 풀 수 있으니까

따라서 대강 점화식을 세우다 보니 다음과 같은 점화식을 세울 수 있었다.

복잡해 보이지만 이러한 방식으로 점화식을 세웠다. 그러나 문제는 이러한 점화식으로 프로그램을 제출 했을때 시간초과가 뜨는 것이었다.......ㅠㅠ

솔직히 나름 식도 잘세우고 어렵던 DP문제를 혼자 풀었던 느낌이라 기분 좋았는데 시간초과가 떠서 무엇을 더 손대야 할지 감을 못잡았다.

그래서 구글링을 해본 결과 저런 형태의 수식인 경우 최적화를 해줄 수 있다.

그게 바로 Knuth Optimization 이다.(blog.myungwoo.kr/98) 관련 자료는 여기서 보면 된다.

간단히 이야기 하자면 

1) 점화식 꼴, 2) 사각방정식, 3) 단조성  이 3가지를 만족하면 새로운 규칙이 추가될 수 있다는 것이다.

새로운 규칙은 아래와 같다.

A[i][j] 는 D[i][j]에서 선택된 k값이다.(즉, D[i][j]를 최소로 만드는 k값)

따라서 A[i][j-1] <= A[i][j] <= A[i+1][j] 를 만족한다. 즉, 모든 i~j까지의 모든 수를 찾아볼 필요없이 조금더 제한된 범위를 탐색할 수 있게 된다는 말이다. 

따라서 이걸 코드로 짜면 아래와 같다.

import sys
case = int(sys.stdin.readline())
for i in range(case):
    n = int(sys.stdin.readline())
    ch = list(map(int,sys.stdin.readline().split()))
    # D선언
    D = [[0 for i in range(n)] for i in range(n)]
    A = [[0 for i in range(n)] for i in range(n)]
    #초기화
    for i in range(n-1):
        D[i][i+1] = ch[i]+ ch[i+1]
        A[i][i+1] = i+1
    #본격적인 연산
    for dig in range(2, n):
        for i in range(n-dig):
            j = i + dig
            min = 100000000
            for k in range(A[i][j-1], A[i+1][j]+1):
                tmp = D[i][k-1] + D[k][j]
                if min > tmp:
                    min = tmp
                    A[i][j] = k
            D[i][j] = min  + sum(ch[i:j+1])
    print(D[0][n-1])

이 코드를 통해 겨우 문제를 풀 수 있었다. 솔직히 Knuth optimization이 어떻게 증명되는지도 모르고 문제를 해결했다. 그래도 학교에서 알고리즘 수업을 들으며 DP의 점화식을 몇번 세우다 보니 처음에 문제 접근에는 성공한거 같아서 기쁘다. 다른 문제도 분발해서 풀자