[프로그래머스,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을 반환한다. 

 

 

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;
    }
}