Life Engineering
[BOJ 11049] 행렬 곱셈 순서 (Java) 본문
https://www.acmicpc.net/problem/11049
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main_BOJ_11049 {
static int N;
static int[][] sizes;
static int[][] dp;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=null;
N=Integer.parseInt(br.readLine());
sizes=new int[N+1][2];
dp=new int[N+1][N+1];
for (int i=1; i<=N; i++) {
st=new StringTokenizer(br.readLine());
sizes[i][0]=Integer.parseInt(st.nextToken());
sizes[i][1]=Integer.parseInt(st.nextToken());
}
for (int len=2; len<=N; len++) {
for (int i=1; i<=N-len+1; i++) {
int j=i+(len-1);
dp[i][j]=Integer.MAX_VALUE;
for (int k=i; k<j; k++) {
int a=sizes[i][0], b=sizes[k][1], c=sizes[j][1];
int cnt=a*b*c;
if (dp[i][j]>dp[i][k]+dp[k+1][j]+cnt) {
dp[i][j]=dp[i][k]+dp[k+1][j]+cnt;
}
}
}
}
System.out.println(dp[1][N]);
}
}
점화식을 유도하는 dp 문제.
주의할 점은 행렬의 크기를 저장하는 배열을 만들어 cnt 값을 구하는 것이다.
(i, k), (k+1, j)를 곱한다면 i의 행xk의 열xj의 열로 곱셈 횟수가 정해진다.
'Problem Solving' 카테고리의 다른 글
[SWEA 5604] 구간 합 (Java) (0) | 2022.04.13 |
---|---|
[SWEA 9760] Poker Game (Java) (0) | 2022.04.12 |
[BOJ 20058] 마법사 상어와 파이어스톰 (Java) (0) | 2022.04.11 |
[BOJ 11066] 파일 합치기 (Java) (0) | 2022.04.09 |
[프로그래머스] 가장 긴 팰린드롬 (Java) (0) | 2022.04.08 |