배움과 성장/알고리즘·문제풀이
백준 11049 행렬 곱셈 순서 Java: 구간 DP 점화식 도출
백준 11049번 ‘행렬 곱셈 순서’는 행렬의 순서를 바꾸지 않고 괄호를 어디에 칠지 정해 scalar multiplication 횟수를 최소화하는 문제다. A×B×C의 결과는 같아도 (A×B)×C와 A×(B×C)의 계산량은 다르다.백준 11049번 행렬 곱셈 순서DP 상태를 구간으로 잡는다dp[start][end]를 start번부터 end번 행렬까지 곱하는 최소 비용으로 둔다. 마지막 곱셈 직전에 구간을 start..middle과 middle+1..end로 나눴다고 생각하면 세 비용이 필요하다.왼쪽 구간을 하나의 행렬로 만드는 비용오른쪽 구간을 하나의 행렬로 만드는 비용완성된 두 행렬을 마지막으로 곱하는 비용행렬 i의 크기를 row[i] × column[i]라고 하면 점화식은 다음과 같다.dp[star..