[Gold III]
https://www.acmicpc.net/problem/11049
11049번: 행렬 곱셈 순서
첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같
www.acmicpc.net
풀이
[백준] 10942. 팰린드롬? - 파이썬 [백준] 9252. LCS 2 - 파이썬 [백준] 7579. 앱 - 파이썬
최근 풀었던 위 3개의 DP 문제와 크게 다를 것이 없었던 문제.
근데 DP는 DP인 걸 알아도.. 문제마다 다른 상황에 맞춰서 풀이를 생각해내기 쉽진 않음.
그리고 Line 28의 i += 1
이거 하나 빼먹어서 30분동안 찾았다.......
자세한 설명은 주석으로 대체.
N = int(input()) mat = [] for _ in range(N): r, c = map(int, input().split()) mat.append((r, c)) # NxM 행렬과 MxK 행렬을 곱하면, NxMxK. # dp[i][j]는 i+1번째 행렬부터, j+1번째 행렬까지 곱했을 때의 곱셈 연산 횟수의 minimum. # k = i ~ j-1 사이의 임의의 값일 때, # dp[i][j] = dp[i][k] + dp[k+1][j] + mat[i][0]*mat[k][1]*mat[j][1] 의 값들 중 최소값. dp = [[0]*N for _ in range(N)] for i in range(N-1): dp[i][i+1] = mat[i][0]*mat[i+1][0]*mat[i+1][1] for L in range(2, N): i = 0 j = L while j < N: dp[i][j] = 2**31 for k in range(i, j): dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + mat[i][0]*mat[k][1]*mat[j][1]) i += 1 j += 1 print(dp[0][N-1])