[백준 11049번 '행렬 곱셈 순서']
https://www.acmicpc.net/problem/11049
[접근방식]
다이나믹 프로그래밍을 이용하여 해결한다.
DP 배열의 정의는 다음과 같다.
"dp[i][j] : i번째 행렬부터 j번째 행렬까지 최소 곱셈 연산수"
작은 집합부터 계산해 나가 궁극적으로 0 ~ n-1 까지의 행렬의 최소 곱셈 연산수를 구한다.
'''
곱셈 연산 단위 : 2개 - [(0, 1), (1, 2), (2, 3), (3, 4), ... , (8, 9)]
곱셈 연산 단위 : 3개 - [(0, 1, 2), (1, 2, 3), (2, 3, 4), (3, 4, 5), ... , (7, 8, 9)]
...
곱셈 연산 단위 : 10개 - [(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)]
'''
위와 같이 모든 경우를 세세하게 구해 궁극적으로 0 ~ 9 까지 행렬 곱연산수의 최솟값을 구한다.
"dp[i][j]" 는 다음과 같은 연산으로 정의된다. (i <= k <= j)
"i ~ j 행렬까지의 최소 곱셈 연산수"
= "i ~ k 행렬까지의 최소 곱셈 연산수"
+ "k+1 ~ j" 행렬까지의 최소 곱셈 연산수"
+ "위 두 행렬의 최소 곱셈 연산수"
[Java 코드]
/**
* BOJ_11049 행렬 곱셈 순서
* https://www.acmicpc.net/problem/11049
* keyword -
*/
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[][] matrices = new int[N][2];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
matrices[i][0] = Integer.parseInt(st.nextToken());
matrices[i][1] = Integer.parseInt(st.nextToken());
}
//dp 정의 : i번째 행렬부터 j번째 행렬까지의 곱의 최소 연산수
int[][] dp = new int[N][N];
for (int len = 1; len < N; len++) { //곱셈 연산 단위 -> index 차이
for (int i = 0; i + len < N; i++) {
int j = i + len;
dp[i][j] = Integer.MAX_VALUE;
/**
* i ~ k 까지 곱셈 연산 수
* k+1 ~ j 까지 곱셈 연산 수
* 두 행렬의 곱셈 연산 수
*/
for (int k = i; k < j; k++) {
int cost = dp[i][k] + dp[k + 1][j] + matrices[i][0] * matrices[k][1] * matrices[j][1];
dp[i][j] = Math.min(dp[i][j], cost);
}
}
}
//0 ~ n-1 까지 곱연산수 최솟값
System.out.println(dp[0][N - 1]);
}
}
[Rewind]
1. 어려웠던 점
- 문제 해결 접근 방식을 제대로 알지 못했다.
- DFS 방식을 통해 모든 경우를 탐색하는 방식을 생각했지만, 비효율적인것 같아 철회했다.
- DP 배열의 정의를 생각해내지 못했고, 그 결과로 문제 역시 해결하지 못했다.
- "곱셈 연산 단위" 라는 것을 이해하지 못했다.
- DP 해결 방식의 기본적인 정의인 "문제를 가장 작은 단위로 나눠 해결하고, 이를 저장하여 불필요한 연산을 줄인다." 라는 것을 잊었다.
2. 알게된 점
- DP문제의 새로운 유형을 알게 되었다.
- DP문제의 정의를 다시 일깨웠다.
3. 개선방안
- 잘모르겠다.
