글 읽기 - 행렬 곱셈 순서 문제에서 크누스 최적화 적용이 안되는 이유

ldh5730 4년 전 0

이 문제에서

크누스 최적화를 사용할 수 있는 지(단조성 증가와 사각부등식 만족하는지)따져볼 때

cost[i][j] = array[i][0]*array[k][1]*array[j][1] (이 때 k는 dp를 만족하는 k 값) 으로 보면 될까요?

input 값이

다음 과 같다고 할 때

위의 cost 식이 맞다는 전제하에 Cost배열이 다음과 같이 나오는 데요

C == [[0, 30, 60, 30], [0, 0, 36, 12], [0, 0, 0, 24], [0, 0, 0, 0]]

제가 단조성 증가를 만족하는 지 확인해보면 C[0][3] >= c[1][2] -> 30>=36 으로 만족하지 않고

사각 부등식을 만족하는 지 확인해봐도 C[0][3] + C[1][2] >= C[0][2] + C[1][3} -> 30 + 36 >= 60 + 12 으로 역시 만족하지 않는 데

이 문제는 사각부등식과 단조성 증가 모두를 만족하지 않아서 크누스 최적화로 풀 수 없다고 생각하면 될까요?

N = int(input())
array = [tuple(map(int,input().split())) for _ in range(N)]
result = [[10**9]*N for _ in range(N)]
C = [[0]*N for _ in range(N)]
for i in range(N) :
    result[i][i] = 0
    C[i][i] = 0


for l in range(1,N) :
    for j in range(l,N) :
        i = j-l
        for k in range(i,j) :
            if result[i][j] > result[i][k] + result[k+1][j] + array[i][0]*array[k][1]*array[j][1] :
                result[i][j] = result[i][k] + result[k+1][j] + array[i][0]*array[k][1]*array[j][1]
                C[i][j] = array[i][0]*array[k][1]*array[j][1]

print(C)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

행렬 곱셈 순서 문제에서 크누스 최적화 적용이 안되는 이유

ldh5730 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말