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

   문제

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

이전문제를 풀었더면 어렵지 않게 풀수있다.

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())
 
matrix=[list(map(int,sys.stdin.readline().split())) for _ in range(N)]
 
 
dp=[[0]*N for _ in range(N)]
 
for x in range(1,N):#거리가 x인 것까지
    for i in range(N-x):#i부터 시작
        j=i+x
        dp[i][j]=99999999999999
        for k in range(i,j):#두 행렬의 곱에서 나오는 추가비용계산해서 더해주기
            dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+matrix[i][0]*matrix[k][1]*matrix[j][1])
 
 
print(dp[0][N-1])

이번문제는 python으로는 시간초과가 났다.

이전에 사용하였던 knuth's optimization 최적화 방법은 아래 조건을 만족하지 못해서 사용할수

 없다.

조건 2) Quadrangle Inequalty (사각부등식)

$\mathrm{<span\; style="font-size:\; 14pt;">C</span>}<span\; style="font-size:\; 14pt;">[</span>\mathrm{<span\; style="font-size:\; 14pt;">a</span>}<span\; style="font-size:\; 14pt;">]</span><span\; style="font-size:\; 14pt;">[</span>\mathrm{<span\; style="font-size:\; 14pt;">c</span>}<span\; style="font-size:\; 14pt;">]</span><span\; style="font-size:\; 14pt;">+</span>\mathrm{<span\; style="font-size:\; 14pt;">C</span>}<span\; style="font-size:\; 14pt;">[</span>\mathrm{<span\; style="font-size:\; 14pt;">b</span>}<span\; style="font-size:\; 14pt;">]</span><span\; style="font-size:\; 14pt;">[</span>\mathrm{<span\; style="font-size:\; 14pt;">d</span>}<span\; style="font-size:\; 14pt;">]</span><span\; style="font-size:\; 14pt;">\le </span>\mathrm{<span\; style="font-size:\; 14pt;">C</span>}<span\; style="font-size:\; 14pt;">[</span>\mathrm{<span\; style="font-size:\; 14pt;">a</span>}<span\; style="font-size:\; 14pt;">]</span><span\; style="font-size:\; 14pt;">[</span>\mathrm{<span\; style="font-size:\; 14pt;">d</span>}<span\; style="font-size:\; 14pt;">]</span><span\; style="font-size:\; 14pt;">+</span>\mathrm{<span\; style="font-size:\; 14pt;">C</span>}<span\; style="font-size:\; 14pt;">[</span>\mathrm{<span\; style="font-size:\; 14pt;">b</span>}<span\; style="font-size:\; 14pt;">]</span><span\; style="font-size:\; 14pt;">[</span>\mathrm{<span\; style="font-size:\; 14pt;">c</span>}<span\; style="font-size:\; 14pt;">]</span><span\; style="font-size:\; 14pt;">,</span>\mathrm{<span\; style="font-size:\; 14pt;">a</span>}<span\; style="font-size:\; 14pt;">\le </span>\mathrm{<span\; style="font-size:\; 14pt;">b</span>}<span\; style="font-size:\; 14pt;">\le </span>\mathrm{<span\; style="font-size:\; 14pt;">c</span>}<span\; style="font-size:\; 14pt;">\le </span>\mathrm{<span\; style="font-size:\; 14pt;">d</span>}$

조건 3) Monotonicity (단조성)

C[b][c]≤C[a][d],a≤b≤c≤d

pypy3으로는풀수있으나 이번문제는 O(N^3)의 시간복잡도를 최적화 시킬 방법을 찾지

못했다.