Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

23. 동적 계획법2

조금 더 어려운 동적 계획법 문제를 풀어 봅시다.

Java / Python

2. 행렬 곱셈 순서

11049번

행렬을 곱하는 최소 비용을 구하는 문제

이번 문제는 행렬 N개의 크기가 주어졌을 때, 모든 행렬을 곱하는데 필요한 곱셈 연산의 횟수의 최솟값을 구하는 프로그램을 작성하는 문제입니다. 행렬을 입력으로 주어진 순서대로 계산해야 합니다.

• Java

import java.io.*;
import java.util.*;

public class Main {
	static int[][] A;
	static int[][] dp;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
   
		int N = Integer.parseInt(br.readLine());
		A = new int[N][2];
		dp = new int[N][N]; 
        
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());   
			A[i][0] = Integer.parseInt(st.nextToken());
			A[i][1] = Integer.parseInt(st.nextToken());
			Arrays.fill(dp[i], Integer.MAX_VALUE);       
		}
		bw.write(solve(0, N - 1) + "\n");  
        
		bw.flush();
		bw.close();
		br.close();
	}
	public static int solve(int start, int end) {
		if(start == end) return 0;
		if(dp[start][end]!= Integer.MAX_VALUE) return dp[start][end];
        
		for(int i = start; i < end; i++) {
			int cost = solve(start, i) + solve(i+1, end) + A[start][0] * A[i][1] * A[end][1];
			dp[start][end] = Math.min(dp[start][end], cost);
		}
		return dp[start][end];
	}
}

• Python

• Python으로는 시간초과가 나서, PyPy3로 제출해야 합니다.

import sys
 
N = int(sys.stdin.readline())
matrix = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]
dp = [[0] * N for _ in range(N)]

for i in range(1, N): 
    for j in range(0, N-i):   
        dp[j][j+i] = 2**32 # 최댓값
        for k in range(j, j+i): 
            dp[j][j+i] = min(dp[j][j+i], dp[j][k] + dp[k+1][j+i] + matrix[j][0] * matrix[k][1] * matrix[j+i][1])

print(dp[0][N-1])