[백준] 행렬 곱셈 순서 Java

https://www.acmicpc.net/problem/11049

11049번: 행렬 곱셈 순서

 

조건

 

주어진 행렬은 인접한 행렬끼리만 곱연산이 가능

 

 

풀이

 

n개의 행렬을 저장하고 있는 배열 input[][]

i ~ j 까지 곱연산의 최소 횟수를 저장하는 배열 dp[][]

 

 

우선 dp 배열의 값 초기화

 

i~i 의 곱연산 회수는 0이기 때문에 dp[i][j] = 0

i~ i+1 의 곱연산 횟수는 input[i][0] * input[i][1] * input[i+1][1]

그 외엔 Integer.MAX_VALUE 로

 

 

 

3중 반복문을 통해 간격, 시작점, 중간점을 탐색하며 값 삽입

 

i 는 간격

바로 다음 행렬의 곱연산 횟수는 위에 초기화에서 이미 설정해 주었기 때문

임의의 값 n 부터 n+2 까지의 행렬의 최소값을 구하기 위해 2부터 시작

 

j 는 시작점

입력값 처음부터 끝까지 탐색

 

k 는 중간점

시작점(j) ~ 시작점(j) + 간격(i) 의 곱연산 최소값을 구하기 위해 dp 배열에 저장되어있던 이전 값들을 활용

 

 

 

    public void solution11049() throws Exception{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());

        int input[][] = new int[n][n];

        int dp[][] = new int[n][n];
        for(int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(reader.readLine());

            input[i][0] = Integer.parseInt(st.nextToken());
            input[i][1] = Integer.parseInt(st.nextToken());
        }
        

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){

                if(j==i)
                    dp[i][j]=0;
                else if(j==i+1)
                    dp[i][j] = input[i][0] * input[i][1] * input[j][1];
                else
                    dp[i][j] = Integer.MAX_VALUE;
            }
        }


        for(int i=2; i<n; i++){
            for(int j =0; j<n-i; j++){
                for(int k=j; k<j+i; k++){
                    int cnt = input[j][0] * input[k][1] * input[j+i][1];
                    dp[j][j+i] = Math.min(dp[j][j+i], dp[j][k] + dp[k+1][j+i] + cnt);
                }
            }
        }
        System.out.println(dp[0][n-1]);

    }