[백준] 11049 : 행렬 곱셈 순서

문제 출처: https://www.acmicpc.net/problem/11049

---

문제

---

시도

 

손도 못 대고 무력하게 다른 사람의 풀이를 참고했다....

---

풀이

 

이번 문제를 풀 때 가장 고민했던 점은 아래 코드의 `matrix[start][0] * matrix[divide][1] * matrix[end][1]` 부분이었다. 문제에 대한 이해가 부족했던 점도 있었지만 결국 고려해야 했던 점은 start부터 end 까지의 곱셈 연산 횟수였었다.

 

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()); // n : 1 ~ 500

        int[][] dp = new int[n][n];
        int[][] matrix = new int[n][2];
        StringTokenizer st;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            matrix[i][0] = Integer.parseInt(st.nextToken());
            matrix[i][1] = Integer.parseInt(st.nextToken());
        }

        for (int interval = 1; interval < n; interval++) {
            for (int start = 0; start + interval < n; start++) {
            	int end = start + interval;
                dp[start][end] = Integer.MAX_VALUE;

                for (int divide = start; divide < end; j++) {
                    dp[start][end] = Math.min(dp[start][end], dp[start][divide] + dp[divide + 1][end] + matrix[start][0] * matrix[divide][1] * matrix[end][1]);
                }
            }
        }

        System.out.print(dp[0][n - 1]);
    }
}

 

풀이 참고 : https://velog.io/@taurus429/JAVA-%EB%B0%B1%EC%A4%80-11049-%ED%96%89%EB%A0%AC%EA%B3%B1%EC%85%88%EC%88%9C%EC%84%9C

---

알게 된 점

 

이런 문제를 더 많이 풀어봐야겠다.