알고리즘 풀이/Java
[알고리즘][X] 행렬 곱셈 순서
Dong's Universe
2024. 4. 23. 21:42
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
int[][] matrix = new int[N][2];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
matrix[i][0] = Integer.parseInt(st.nextToken());
matrix[i][1] = Integer.parseInt(st.nextToken());
}
int[][] dp = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (i == j) {
continue;
}
dp[i][j] = Integer.MAX_VALUE;
}
}
int[][][] size = new int[N][N][2];
for (int i = 0; i < N; i++) {
for (int j = 0; j < 2; j++) {
size[i][i][j] = matrix[i][j];
}
}
if (N == 1) {
return;
}
for (int i = 0; i < N - 1; i++) {
int m = i;
int n = i+1;
dp[m][n] = size[m][m][0] * size[m][m][1] * size[n][n][1];
size[m][n][0] = size[m][m][0];
size[m][n][1] = size[n][n][1];
}
for (int step = 2; step < N; step++) {
for (int i = 0; i < N - step; i++) {
int m = i;
int n = i + step;
for (int j = 0; j < n - m; j++) {
dp[m][n] = Math.min(dp[m][n], dp[m][m + j] + dp[m + j + 1][n] + size[m][m + j][0] * size[m][m + j][1] * size[m + j +1][n][1]);
}
size[m][n][0] = size[m][n-1][0];
size[m][n][1] = size[n][n][1];
}
}
System.out.println(dp[0][N-1]);
}
}
나의 풀이
- 처음에 점화식을 잘못 세워섰다. 왼쪽 끝과 오른쪽 끝 두 개를 기준으로만 쪼개진다고 생각했다.
- 아래는 리팩토링한 코드. 초기 행렬의 행 또는 열을 알고 있으면 합성 행렬의 행 또는 열을 추론할 수 있다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
int[][] matrix = new int[N][2];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
matrix[i][0] = Integer.parseInt(st.nextToken());
matrix[i][1] = Integer.parseInt(st.nextToken());
}
int[][] dp = new int[N][N];
for (int step = 1; step < N; step++) {
for (int i = 0; i < N - step; i++) {
int m = i;
int n = i + step;
dp[m][n] = Integer.MAX_VALUE;
for (int j = 0; j < n - m; j++) {
dp[m][n] = Math.min(dp[m][n],
dp[m][m + j] + dp[m + j + 1][n] + matrix[m][0] * matrix[m + j][1]
* matrix[n][1]);
}
}
}
System.out.println(dp[0][N - 1]);
}
}