질문 목록 [프로그래머스]

각 행렬의 크기 matrix_sizes 가 매개변수로 주어 질 때, 모든 행렬을 곱하기 위한 최소 곱셈 연산의 수를 return하는 solution 함수를 완성해 주세요.

제한 사항
행렬의 개수는 3이상 200이하의 자연수입니다.
각 행렬의 행과 열의 크기는 200이하의 자연수 입니다.
계산을 할 수 없는 행렬은 입력으로 주어지지 않습니다.

처음 생각한것

상향식 방법과 하향식 방법이있다.
먼저 상향식으로 문제를 풀면 DP문제가 된다. 이 문제 설명이 모호해서 그렇지만 무조건 행렬 앞뒤로 계산이 가능한 배열이다.

상향식으로 생각해보자. 먼저 행렬을 하나씩 곱하는건 의미가 없다 자기자신을 곱하는것이기 때문에.
예로 4개의 행렬 [1,10][10,2][2,15][15,7]가 있다고 치자
행렬 2개를 곱한다면 3번의 연산이 필요하다.
행렬 3개를 곱한다면 이전 행렬 2개 곱한것에 나머지 하나의 행렬이 들어간다.
행렬 4개를 곱한다면 이전 행렬 3개를 곱한것에 나머지 하나의 행렬 혹은 이전 행렬 2개 곱한것이 들어간다.
따라서 DP로 치면 DP[a][b] = DP[a][k] + DP[k+1][b] + (이번 행렬[a][0] 이번 행렬[k][1] 이번 행렬[b][1]) 이라는 공식이 생긴다 (DP[a][k]는 Prifix DP[k+1][b]는 Postfix이다.)
이를 통해서 가장 낮은 DP에서 원하는 answer를 찾아낼수있다.
하향식으로는 반대로 생각하면된다.
가장 원하는 answer를 만들기위해서는 위에서부터 범위를 쪼개서 내려가면된다.

상향식 코드

import java.util.*;
class Solution {
    public int solution(int[][] matrix_sizes) {
        int n= matrix_sizes.length;
        int[][] DP = new int[n][n];   
        int answer = 0; 
 
        for(int i = 0; i < n; i++){ 

            for(int j = 0; j < n-i; j++){ 
            int a = j;  
            int b = j + i;  
            for(int k = a; k < b; k++){
                if(DP[a][b]==0){
                    DP[a][b]=DP[a][k] + DP[k+1][b] + (matrix_sizes[a][0] * matrix_sizes[k][1] * matrix_sizes[b][1]);
                }else{
                    DP[a][b] = Math.min(DP[a][b], DP[a][k] + DP[k+1][b] + (matrix_sizes[a][0] * matrix_sizes[k][1] * matrix_sizes[b][1]));
                }
           
                answer=DP[a][b];
            
       }
    }
}
       
       
        return answer;
    }
} // 상향식으로 문제를 풀면 DP 하향식으로 문제를 풀면 메모이제이션사용...