11049 행렬 곱셈 순서
-
백준 11049 행렬 곱셈 순서Algorithm/BOJ 2021. 4. 21. 14:08
출처: www.acmicpc.net/problem/11049 분류: DP 접근방식 전체 순서를 유지하면서 특정 연산을 해야할 때 연산 순서를 어떻게 해야 최소가 될까? 에 관한 문제였습니다. 11066 파일합치기 와 유사한 문제였다는 생각이 드네요. 핵심 아이디어는 X ~ Y까지 연산의 최소값을 DP에 계속 저장해나가는데, X ~ Y까지 연산의 최솟값은 (X~K) + (K~Y) 연산들 중 최소를 찾아나가는 것입니다. 문제의 예시를 가지고 생각해보겠습니다. 각 행렬이 배열에 들어있다고 생각하면, (5x3) - 0 (3x2) - 1 (2x6) - 2 0 ~ 1 까지의 최소값은 dp[0][1], 0 ~ 2 까지의 최소값은 dp[0][2] 에 담는 것입니다. 0 ~ 2 까지의 최솟값은 ( [0][1] 을 먼저 ..