✓

태그:

22. 동적 계획법 2 CLASS 5 ESSENTIAL

주어진 행렬의 중간 결과를 만드는 비용의 최소값을 구합니다.

풀이 비스무리한거 보기

주어진 행렬들을 두 개씩 곱해서 전체 행렬들의 곲을 구할 때 최소의 비용을 구하는 문제입니다. 이 문제는 ③ 11066 - 파일 합치기와 유사한 풀이의 DP 문제인데, x번 행렬부터 y번 행렬까지의 곱을 구할 때 필요한 최소 비용을 저장합니다. 곱을 구할 범위가 좁은 부분곱(?)의 비용부터 구해나갑니다. 관계식은 아래와 같게 됩니다.

cost[a][b] = min([cost[a][x] + cost[x + 1][b] + left[a] * right[b] * right[x] for x in range(a, b)])

위에서 cost[a][b]는 a번 행렬부터 b 행렬까지의 부분곱을 구할 때의 최소 비용, left[x]는 x번 행렬의 행, right[x]는 열의 크기입니다. 위의 식을 이용하면 결과값을 빠르게 구할 수 있습니다.

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-01-25 22:39:13

---