[백준] 11049번 행렬 곱셈 순서
문제 설명
https://www.acmicpc.net/problem/11049
문제 풀이
- 다이나믹 프로그래밍으로 풀이하였다. (백준 11066번과 유사)
- 문제 풀이에 사용된 점화식은 아래와 같다.
- DP[from][to] : from 인덱스에서 to 인덱스까지 행렬 곱셈 연산 수
- arr[i][0] : i번쨰 행렬 row값, arr[i][1] : i번째 행렬 col값
- DP[from][to] = MIN(DP[from][i] + DP[i+1][to] + arr[from][0] * arr[i][1] * arr[to][1]) (from <= i < to)
소스 코드 (JAVA)
import java.io.*;
public class Main {
public static int N;
public static int INF = 987654321;
public static int[][] arr = new int[500][2];
public static int[][] dp = new int[500][500];
public static void init() {
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
dp[i][j] = INF;
}
public static int solve(int from, int to) {
//기저조건 범위가 1개일 때 곱셈 0번
if (from == to) return 0;
if (dp[from][to] != INF) return dp[from][to];
int result = INF;
for (int i = from; i < to; i++) {
result = Math.min(result, solve(from, i) + solve(i+1, to) + arr[from][0] * arr[i][1] * arr[to][1]);
}
return dp[from][to] = result;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
for (int i = 0; i < N; i++) {
String[] input = br.readLine().split(" ");
arr[i][0] = Integer.parseInt(input[0]);
arr[i][1] = Integer.parseInt(input[1]);
}
init();
bw.write(solve(0, N-1) + "\n");
br.close();
bw.flush();
bw.close();
}
}
Author And Source
이 문제에 관하여([백준] 11049번 행렬 곱셈 순서), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ddongh1122/백준-11049번-행렬-곱셈-순서저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)