728x90
백준 11049 - 행렬 곱셈 순서
https://www.acmicpc.net/problem/11049

문제
크기가 NxM인 행렬 A, MxK인 B를 곱할 때 필요한 곱셈의 연산 수는 총 NxMxK번
행렬 N개를 곱하는데 필요한 곱셈의 연산 수는 행렬을 곱하는 순서에 따라 달라짐
ex. A의 크기 5x3, B의 크기 3x2, C의 크기 2x6인 경우 행렬 곱 ABC
- (AB)C_AB를 먼저 곱하고 C를 곱하는 경우: 5x3x2 + 5x2x6 = 30 + 60 = 90
- A(BC)_BC를 먼저 곱하고 A를 곱하는 경우: 3x2x6 + 5x3x6 = 36 + 90 = 126
입력
첫째 줄: 행렬의 개수 N (1 <= N <= 500)
둘째 줄 ~ N개의 줄: 행렬의 크기 r, c (1 <= r, c <= 500)
항상 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어짐
출력: 입력으로 주어진 행렬을 곱하는데 필요한 곱셈의 연산 최솟값 출력
풀이
`dp[i][j]`: i번째 행렬부터 j번째 행렬까지 곱하는 최소 연산 횟수
행렬을 k에서 나눔
- 왼쪽 계산 비용: `dp[i][k]`
- 오른쪽 계산 비용: `dp[k + 1][j]`
- 두 결과 곱하는 비용
(Ai ... Ak) x (A(k + 1) ... Aj)
- (Ai ... Ak) 결과 크기: rows[i] x cols[k]
- (A(k + 1) ... Aj) 결과 크기: rows[k + 1] x cols[j]
=> `rows[i] * cols[k] * cols[j]`
long cost = dp[i][k] + dp[k + 1][j] + (long) r[i] * c[k] * c[j];
dp[i][j] = Math.min(dp[i][j], cost);
길이가 `len`인 모든 구간 [i, j]를 하나씩 만듦
- `len`: 구간에 포함된 행렬의 개수
- 구간의 시작점: i
- 구간의 끝점: `j = i + len - 1` (인덱스는 1부터 시작)
- ex. len = 2: 행렬 2개짜리 구간
- i = 1 / 포함되는 인덱스: [1, 2] / j = 2
- i = 2 / 포함되는 인덱스: [2, 3] / j = 3
코드
import java.io.*;
import java.util.*;
// 행렬 곱셈 순서
public class boj_11049 {
static int N;
static int[] r, c;
static long[][] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
r = new int[N + 1];
c = new int[N + 1];
dp = new long[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
r[i] = Integer.parseInt(st.nextToken());
c[i] = Integer.parseInt(st.nextToken());
}
for (int len = 2; len <= N; len++) {
for (int i = 1; i + len - 1 <= N; i++) {
int j = i + len - 1;
dp[i][j] = Long.MAX_VALUE;
for (int k = i; k < j; k++) {
long cost = dp[i][k] + dp[k + 1][j] + (long) r[i] * c[k] * c[j];
dp[i][j] = Math.min(dp[i][j], cost);
}
}
}
System.out.println(dp[1][N]);
}
}728x90
반응형
'✏️ > BOJ' 카테고리의 다른 글
| [BOJ/Segment Tree] 백준 11505 - 구간 곱 구하기 (Java) (0) | 2025.12.24 |
|---|---|
| [BOJ/DP] 백준 11066 - 파일 합치기 (Java) (0) | 2025.12.22 |
| [BOJ/Segment Tree] 백준 2042 - 구간 합 구하기 / 10999 - 구간 합 구하기 2 (Java) (0) | 2025.12.20 |
| [BOJ/Greedy] 백준 1700 - 멀티탭 스케줄링 (Java) (0) | 2025.12.16 |
| [BOJ] 백준 1516 - 게임 개발 (Java) (0) | 2025.12.15 |