백준 11049 [python]

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

N = int(input())
A = [[0 for i in range(N)] for i in range(N)]
C = [[[0, 0] for i in range(N)] for i in range(N)]
dp = [[0 for i in range(N)] for i in range(N)]

for i in range(N):
    C[i][i] = list(map(int, input().split()))
for i in range(N - 1):
    A[i][i + 1] = i
    C[i][i + 1] = [C[i][i][0], C[i + 1][i + 1][1]]
    dp[i][i + 1] = C[i][i][0] * C[i][i][1] * C[i + 1][i + 1][1]
    
for a in range(2, N):
    for i in range(N - a):
        j = a + i
        C[i][j] = [C[i][i][0], C[j][j][1]]
        dp[i][j], A[i][j] = min([C[i][k][0] * C[i][k][1] * C[k + 1][j][1] + /
        dp[i][k] + dp[k + 1][j], k] for k in range(i, j))
        
print(dp[0][N - 1])

11066번이랑 똑같다고 생각해서 크누스 최적화를 써서 풀었더니 틀렸다. 이유는 크누스 최적화가 가능하기 위한 조건 중 하나인 C[b][c] <= C[a][d] (a <= b <= c <= d)를 만족하지 않아서 그렇다. 여기서 C는 점화식 DP[i][j] = min(DP[i][k] + DP[k][j]) + C[i][j] (i < k < j)의 C이므로 이 문제에서 C[i][j]는 배열곱 횟수인 N * M * K인 느낌이다. 11066번 문제는 파일을 합치면 당연히 커지므로 이 조건을 만족하지만, 이 문제는 직관적으로 보더라도 C의 값이 커지지 않아 이 조건을 만족하지 않는다.

11066번 문제풀이에 비해 코드를 깔끔하게 썼다.