[Python]동적계획법2 백준 11066

   문제

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

n~m까지의 최소합을 dp[n][m] 이라고 표현햇을때

dp[0][m] 까지의 최소합은

dp[0][0]+dp[1][m]

dp[0][1]+dp[2][m]

......

dp[0][m-1]+dp[m][m]

중 하나일것이다.

코드를 짜보자

import sys
 
n=int(input())
 
while n>0:
    n-=1
    K=int(input())
    file_list=list(map(int,sys.stdin.readline().split()))
    dp=[[0 for _ in range(K)] for _ in range(K)]
    sum=[0]*(K+1)#첫번째부터 K번짹 까지의 파일크기합 한번 합칠때 추가비용
    sum[0]=0
    sum[1]=file_list[0]
    for i in range(1,K+1):#i번째 파일까지의 합
        sum[i]=sum[i-1]+file_list[i-1]
 
    for x in range(1,K+1):#x만큼 더한 구간의 구하기
        for i in range(K-x):#시작위치 i에서 i+x까지 구간 잡아주기
            j=i+x
            dp[i][j]=999999999999
            for k in range(i,j):#시작위치에서 x만큼 더한 위치의 구간을 k를 기준으로 나누어서 계산하여 최솟값을 구한다..
                    dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j+1]-sum[i])
 
 
    print(dp[0][K-1])

이렇게 제출하면 시간 초과가 뜬다

O(N^3)의 시간복잡도를 가지는데  O(N^2)로 줄여주는 최적화 방법이 있다고 한다.

knuth's optimization라고 하는데 아래를 참고하여 코드를 짜보았다.

https://wogud6792.tistory.com/20

import sys
 
n=int(input())
 
while n>0:
    n-=1
    K=int(input())
    file_list=list(map(int,sys.stdin.readline().split()))
    dp=[[0 for _ in range(K)] for _ in range(K)]
    sum=[0]*(K+1)#첫번째부터 K번짹 까지의 파일크기합 한번 합칠때 추가비용
    sum[1]=file_list[0]
    for i in range(1,K+1):#i번째 파일까지의 합
        sum[i]=sum[i-1]+file_list[i-1]
 
    knuth = [[0 for _ in range(K)] for _ in range(K)]  # Knuth's Optimization 각 구간에서 나오는 k 저장
    for i in range(K):#초기화화
        knuth[i][i]=i
 
 
    for x in range(1,K):#x만큼 더한 구간의 구하기
        for i in range(K-x):#시작위치 i에서 i+x까지 구간 잡아주기
            j=i+x
            dp[i][j]=999999999999
            for k in range(knuth[i][j-1],knuth[i+1][j]+1): #범위에 knuh 최적화를 적용
                if k < K - 1 and dp[i][j] > dp[i][k] + dp[k+1][j]+sum[j+1]-sum[i]:#최솟값찾기
                    dp[i][j]=dp[i][k]+dp[k+1][j]+sum[j+1]-sum[i]
                    knuth[i][j]=k
            
    print(dp[0][K-1])
 

다시 풀어봐야할 문제이고 for문이 여러개라 헷갈리는 경우가 많을거 같다.

최적화 부분의 증명도 완벽히 이해할수 있도록 해야겠다.