1. 문제
크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다.
예를 들어, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해보자.
- AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 5×3×2 + 5×2×6 = 30 + 60 = 90번이다.
- BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는 3×2×6 + 5×3×6 = 36 + 90 = 126번이다.
같은 곱셈이지만, 곱셈을 하는 순서에 따라서 곱셈 연산의 수가 달라진다.
행렬 N개의 크기가 주어졌을 때, 모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값을 구하는 프로그램을 작성하시오. 입력으로 주어진 행렬의 순서를 바꾸면 안 된다.
2. 풀이
ABCD...Z까지 행렬곱셈을 한다고 했을 때, start=A, end=Z다.
그 사이에서 mid를 옮겨가며 앞묶음과 뒤묶음으로 나눠 곱셈을 생각한다.
(앞)*(뒤)로 나눴을 때, 그 연산 횟수는 앞묶음 연산횟수 + 뒷묶음 연산횟수 + (앞x뒤 연산횟수)가 된다.
여기서 앞, 뒤 각각의 연산횟수는 dp에 저장되어 있다.
앞x뒤 연산횟수를 새로 구해야 하는데, 이 값은
"앞묶음의 가장 처음 행렬 행 숫자 x 앞 묶음의 가장 뒷 행렬의 열 숫자(=뒷 묶음의 가장 처음 행렬 행 숫자) x 뒷 묶음의 가장 뒷 행렬의 열 숫자"
로 구할 수 있다.
start부터 end 사이를 mid로 쪼개 연산횟수를 구하기 때문에 거리(end-start)순으로 dp를 채워나간다.
mid를 옮겨가면서 탐색할 때, min값을 골라 저장하므로 dp의 초기값을 Integer.MAX_VALUE로 한다.
초기값으로 배열을 채우면서 dp[i][i]를 0으로 저장한다. 자기 자신을 곱하지 못하기 때문이다. (연산횟수 0)
탐색이 끝난 후에는 dp[0][N-1]을 출력한다.
import java.io.*;
import java.util.*;
public class BOJ_11049_행렬곱셈순서 {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(in.readLine());
int[][] arr = new int[N][2];
StringTokenizer st;
for(int i=0;i<N;i++){
st = new StringTokenizer(in.readLine());
arr[i][0] = Integer.parseInt(st.nextToken());
arr[i][1] = Integer.parseInt(st.nextToken());
}
int[][] dp = new int[N][N];
for(int i=0;i<N;i++){
Arrays.fill(dp[i], Integer.MAX_VALUE);
dp[i][i] = 0;
}
int end;
for(int len=1;len<N;len++){
for(int start=0;start<N-len;start++){
end = start+len;
int tmp = arr[start][0]*arr[end][1];
for(int mid = start;mid<end;mid++){
dp[start][end] = Math.min(dp[start][end],
dp[start][mid]+dp[mid+1][end]+tmp*arr[mid][1]);
}
}
}
System.out.println(dp[0][N-1]);
}
}
3. 결과
arr[start][0]*arr[end][1]부분이 중복계산되는 것 같아서 tmp로 뺐는데 오히려 시간이 더 걸렸다. 이유는 모르겠다!
'코딩테스트 > BOJ' 카테고리의 다른 글
[BOJ] 1202 보석 도둑 - JAVA (0) | 2023.06.28 |
---|---|
[BOJ] 1937 욕심쟁이 판다 - JAVA (0) | 2023.06.27 |
[BOJ] 18428 감시 피하기 - JAVA (0) | 2023.06.25 |
[BOJ] 10942 팰린드롬? - JAVA (0) | 2023.06.24 |
[BOJ] 17086 아기 상어 2 - JAVA (0) | 2023.06.21 |
댓글