sm 기술 블로그
187. 11049(행렬 곱셈 순서) - 자바 본문
import java.util.*;
import java.io.*;
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[][] rc = new int[N][2];
int[][] dp = new int[N][N];
for (int i = 0; i < N; i++) {
String[] tmp = br.readLine().split(" ");
rc[i][0] = Integer.parseInt(tmp[0]);
rc[i][1] = Integer.parseInt(tmp[1]);
}
for (int i = 1; i < N; i++) {
for (int x = 0; x < N - i; x++) {
int y = x + i;
dp[x][y] = (int) Math.pow(2, 32);
for (int k = x; k < y; k++) {
dp[x][y] = Math.min(dp[x][y], dp[x][k] + dp[k + 1][y] + rc[x][0] * rc[k][1] * rc[y][1]);
}
}
}
System.out.println(dp[0][N-1]);
}
}
문제요약
행렬의 곱셈 연산이 제일 적게 이행하는 최솟값을 구하라.
설명
행렬의 곱셈식은
이다.
따라서 연산 횟수는 x*z*y가 된다.
이 식을 기억하고 입력 예제를 보자.
다음과 같이 행렬의 크기가 주어지면
1. 5 * 3 * 2 + 5 * 2 * 6 = 30 + 60 = 90
2. 3 * 2 * 6 + 5 * 3 * 6 = 36 + 90 = 126
으로 1번의 연산이 더 적다.
일단 DP 리스트에서 우리는 회색 대각선 기준 윗부분만 사용할 것이다.
계산은 각 색깔별로 진행된다.
DP[0][1] -> DP[1][2] -> DP[2][3] -> DP[3][4] -> DP[0][2] -> ... -> DP[0][4]
로 진행되며 DP[0][4] 가 출력값을 지니게 된다.
for (int i = 1; i < N; i++) {
for (int x = 0; x < N - i; x++) {
먼저 i는 회색 대각선 하단 부분은 사용하지 않기 위해서 설정한 것이다.
따라서 x를 N-i만큼만 진행되도록 하였다. (다음 행이 될때마다 사용하는 주소가 줄어든다. 4 -> 3 -> 2 -> 1)
int y = x + i;
y는 i + x로 설정하면 될것이다.
예를들어
i가 1번째에서 x가 0 이면 arr[x][y] = arr[0][1] 이고, x가 1이면 arr[x][y] = arr[1][2] 이런식으로 진행된다.
dp[x][y] = (int) Math.pow(2, 32);
for (int k = x; k < y; k++) {
dp[x][y] = Math.min(dp[x][y], dp[x][k] + dp[k + 1][y] + rc[x][0] * rc[k][1] * rc[y][1]);
}
}
}
최소 값을 구하기 위해서 초반 셋팅값은 2의 32제곱으로 정해주었다.
연산횟수는 2의 31승 -1 보다 작거나 같기 때문에 최대한의 크기로 설정해 준것이다.
이제 본격적인 비교가 들어가는데 k를 x~y범위로 하여 계산을 진행한다.
아까 위에서 연산 횟수를 구할 때 식을 보면
[x][0] + ([x][1] 혹은 [y][0]) + [y][1] 인 것을 볼 수 있다.
즉, [x][0] + ?? + [y][1] 이라는 것을 알 수 있고, ??는 x 혹은 y가 들어가게 되어 k를 위와같이 설정해주었다.
DP[x][k] + DP[k+1][y]는 다음을 표시한것이다
빨간색 (현재)를 구하기 위해 노란색(DP[x][k] + DP[k+1][y]) 부분을 이용한 것이다.
결국 마지막 부분까지 하면 총 계산이 끝난 거고
x가 0 y가 끝부분을 가리 키는 빨간색 부분이 답이 된다.
'문제 > 백준_자바' 카테고리의 다른 글
189. 10942(팰린드롬?) - 자바 (0) | 2022.09.04 |
---|---|
188. 1520(내리막 길) - 자바 (0) | 2022.09.03 |
186. 11066(파일 합치기) - 자바 (0) | 2022.08.25 |
185. 1655(가운데를 말해요) - 자바 (0) | 2022.08.23 |
184. 11286(절댓값 힙) - 자바 (0) | 2022.08.22 |