[java 백준] 11049번 행렬 곱셈순서

import javax.sound.midi.Patch;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
class Main {
 
    public static int n;
    public static int [][]arr;
 
    public static int[][]dp;
 
 
 
 
    public static void main(String args[]) throws NumberFormatException, IOException {
 
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        n=Integer.parseInt(br.readLine());
        arr=new int[n][2];
        dp=new int[n][n];
 
        for(int i=0;i<n;i++){
            st=new StringTokenizer(br.readLine());
            arr[i][0]=Integer.parseInt(st.nextToken());
            arr[i][1]=Integer.parseInt(st.nextToken());
 
        }
        //인접하는 경우
        for(int i=0;i<n-1;i++){
            dp[i][i+1]=arr[i][0]*arr[i][1]*arr[i+1][1]; //중간에 들어가는걸 곱해줬어야
 
        }
 
        
        //dp[i][j] i번째 인덱스부터 j번째 인덱스까지 연산수의 최소
        //dp[i][i]=0임!!
       for(int gap=2;gap<n;gap++){
           for(int start=0;start<n-gap;start++){
               int end=start+gap;
               dp[start][end]=Integer.MAX_VALUE;
               for(int mid=start;mid<end;mid++){
                   dp[start][end]=Math.min(dp[start][end],dp[start][mid]+dp[mid+1][end]+arr[start][0]*arr[mid][1]*arr[end][1]); //왜 arr[mid][0]이 아니고
                   //arr[mid][1]이여야 하나면 start와 mid가 같을 수 있기 때문에
                   //System.out.println("start: "+start+" mid: "+mid+" dp: "+dp[start][mid]+" end: "+end+" dp: "+dp[mid+1][end]);
               }
 
           }
       }
 
        System.out.println(dp[0][n-1]);
 
 
 
 
 
 
 
 
 
    }
 
}

 

다음번에 만났을 때는 end를 기준으로 하지말고 이번처럼 gap을 기준으로 점화식을 짜볼 것 !