첫째 줄에 행렬의 개수 N(1 ≤ N ≤ 500)이 주어진다.
둘째 줄부터 N개 줄에는 행렬의 크기 r과 c가 주어진다. (1 ≤ r, c ≤ 500)
항상 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어진다.
첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다.
정답은 2^31-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 2^31-1보다 작거나 같다.
dp[i][j]를 i번째 행렬부터 j번째 행렬까지의 곱셈 연산의 최소 횟수라고 정의해두자.
그렇다면
dp[i][j] = dp[i][k] + dp[k + 1][j] + ( maps[i][0] * maps[k][1] * maps[j][1] )
DP를 뭘로 둘지만 생각하면 금방 풀 수 있는데
아직은 한 번에 생각나질 않는다..
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int[][] maps;
static int[][] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
maps = new int[n][2];
dp = new int[n][n];
StringTokenizer st;
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
maps[i][0] = Integer.parseInt(st.nextToken());
maps[i][1] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if(i==j) dp[i][j] = 0;
else dp[i][j] = Integer.MAX_VALUE;
}
}
for (int i = 1; i < n; i++) {
for (int j = 0; i + j < n; j++) {
calc(j, i + j);
}
}
System.out.println(dp[0][n - 1]);
}
public static void calc(int start, int end) {
for (int i = start; i < end; i++) {
int cost = dp[start][i] + dp[i + 1][end] + maps[start][0] * maps[i][1] * maps[end][1];
dp[start][end] = Math.min(dp[start][end], cost);
}
}
}