[프로그래머스,Java] Level3: 최적의 행렬곱셈
문제분석
연속 행렬의 연산수를 최소화 시키는 문제다.
계산을 할 수 없는 행렬은 입력으로 주어지지 않는게 특징이다.
즉, 연속된 행렬의 인접한 숫자는 무조건 같다.
1. 첫번째 접근
연속된 두 행렬을 merge , 계산하면 인접한 숫자는 사라진다.
즉, 인접한 숫자를 "먼저" 없애면 연산을 최적화 할수 있다고 생각했다.
즉, [5,3],[3,10],[10,6] 이면 인접한 숫자 10을 먼저 소거시키면 적은 연산을 이룰수 있을줄알았다.
1. 인접한 숫자와 위치를 먼저 뽑는다.
2. 인접한 숫자가 제일큰 순서대로 정리한뒤, 그 위치에있는 2개의 행렬을 merge한뒤에 삽입한다.
이 과정을 행렬이 한 개 남을때 까지 반복한다.
=> 틀림
이유는, 추측이 잘 안되지만.. 인접한 숫자가 가장 큰 순서대로 뽑아 연산하는것은
어떠한 특수케이스를 위반하는것 같다.
다른 사람의 도움
이 문제는 DP였다.
DP 문제임을 눈치는 챘지만, 점화식을 짜야하는 dp는 많은 수학적 지식이 필요하다.
따라서, 수학적 지식을 다른사람에게 빌려 코딩을 짜보았다.
https://youtu.be/ocZMDMZwhCY?t=279
누군가 올려주신, 최적의 행렬 횟수 알고리즘!
요약은, 행렬을 2개의 덩어리 Left, Right로 쪼개어 생각하는것이다.
그리고 행렬의 인덱스를 다음과 같이 생각한다.
[0,1],[1,2],[2,3],[3,4],[4,5] 즉 , 0~1 , 1~2 같은 범위는 무조건 0이라고 생각할수있다.
이 두가지가 핵심 발상이었다.
문제풀이:
dp 문제가 어려운 그 첫번째,
메모이제이션을할 dp배열을 어떻게 의미를 부여할지다.
이 dp배열을 [시작지점][끝나는지점] 으로 설정하였다.
이걸로, 모든 행렬의 연산을 탐색하되, 최적의 연산을 뽑을수있다.
그 다음 , [시작][끝지점] 을 계산할 로직이다.
간단하게 말하자면 A 덩어리 (left) 와 B 덩어리(right)를 쪼갠뒤,
A덩어리와 B덩어리의 merge했을때의 횟수를 저장한다 = current
그 후, A덩어리에서의 최적의 횟수 + B덩어리의 최적횟수 + A 와 B를 더했을때 최적의횟수를
다양한 케이스중에 최소값을 구한뒤 반환한다.
A 덩어리와 B덩어리의 최적값을 찾는 로직이다.
dp[s][e]가 값이 존재한다면, 바로 dp값을 반환한다.
만약, 값이 존재하지 않는다면 재귀를 탄다. (cal 연산)
여기서 s,e 가 차이가 1이면 0을 반환한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
import java.util.*;
class Solution {
int[][] dp;
int[][] matrix;
public int solution(int[][] matrix_sizes) {
int answer = 0;
matrix= matrix_sizes;
int size= matrix_sizes.length;
dp = new int[size+1][size+1];
return cal(0,size);
}
public int find(int s,int e){
if(dp[s][e]==0){
dp[s][e]=cal(s,e);
}
return dp[s][e];
}
public int cal(int s,int e){
if(e-s==1){
return 0;
}
int as =Integer.MAX_VALUE;
for(int m=s+1;m<e;m++){
int left=find(s,m);
int right=find(m,e);
int current=matrix[s][0]*matrix[m][0]*matrix[e-1][1];
as = Math.min(as,left+right+current);
}
return as;
}
}
|
cs |