[백준] 단계별로 풀어보기(단계:23,동적 계획법 2,JAVA)11049번, 행렬 곱셈 순서

문제 링크

11049번: 행렬 곱셈 순서

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

동적계획법이란 위 문제와 같이 동일한 연산을 계속 반복하여 비효율적으로 코드가 실행되어 그것을 향상시키기 위하여반복되는 연산의 결과를 따로 저장하여 적재적소에 코드가 더 효율적으로 만드는 방법입니다.

단계별 풀어보기 문제에서 동적계획법2에 이전 문제 11066번 파일 합치기를 풀어보았다면 이 문제는 쉽게 풀렸을 것이라고 생각합니다.(아래 링크는 제가 풀었던 방법입니다.)

[백준] 단계별로 풀어보기(단계:23,동적 계획법 2,JAVA)11066번, 파일 합치기

메모이제이션 DP[j][i]일 때 j번째 행렬부터 i번째 형렬를 곱했을 때 최소값을 저장하는 것을 반복으로 DP를 모두 저장하였을 때 DP[1][K]의 값을 구하는 것으로 행렬들을 곱했을 때 최소 연산의 수를 구할 수 있습니다.

 

예를 들어 A1([5][3]), A2([3][2]) ,A3([2][6]), A4([6][4]) 존재시

 

DP[1][2]는 A1,A2를 곱했을 때 최소 연산의 수

 

DP[1][3]은 A1, A2, A3를 곱했을 때 최소연산의 수

 

DP[2][4]는 A2, A3, A4를 곱했을 때 최소 연산의 수으로 표현할 수 있습니다.

 

최소 연산의 수를 구할 시

 

A1, A2, A3가 존재하면 행렬를 곱할 수 있는 경우의 수는

 

1. (A1, A2), A3 : A1과 A2를 먼저 곱한 후 A3와 곱하기

 

2. A1, (A2, A3) : A2와 A3를 먼저 곱한 후 A1과 곱하기

 

※ 문제에서 입력값의 주어진 행렬의 크기를 고려하면 인접한 행렬끼리만 곱할 수 있다는 조건을 얻을 수 있어서 A1과 A3는 곱할 수 없습니다. 

 

식으로 살펴보면

 

1번에서 (A1, A2)는 DP[1][2]로 표현하고 A3은 DP[3][3]으로 표현한 뒤

(A1, A2) 과 A3의 행렬은 마지막에 곱해지기 때문에 A1*A2와 A3 행렬의 최소 연산의 수를 더해주어야 합니다.

 

※ matrix는 행렬의 Row, Col 크기를 저장한 배열입니다.

 

DP[1][2] + DP[3][3] + matrix[1][0] * matrix[2][1] * matirx[3][1]이 나옵니다.

2번도 1번과 동일하게 표현하면

 

DP[1][1] + DP[2][3] + matrix[1][0] * matrix[1][1] * matrix[3][1]이 나옵니다.

 

 

다른 예시로 A2, A3, A4가 합쳐진다면(범위 2~4)

 

(A2, A3), A4 : DP[2][3] + DP[4][4] + matrix[2][0] * matrix[3][1] * matrix[4][1]

 

A2 , (A3, A4) : DP[2][2] + DP[3][4] + matrix[2][0] * matrix[2][1] * matrix[4][1]

 

※matrix[j][0] * matrix[s][1] * matrix[i][1]는 마지막 2행렬의 곱을 나타내는 것입니다.

위 식은 N * M * K를 표현한 것입니다.

 

예를 들어 A1([5][3]), A2([3][2]) ,A3([2][6]), A4([6][4]) 존재시

 

DP[1][4]를 구할 때 A1,A2 와 A3,A4로 짝지어진 경우

 

(A1, A2) 결과 배열의 크기는 [5][2]

 

(A3, A4) 결과 배열의 크기는 [2][4]

 

(A1, A2)와 (A3, A4) 곱은 5 * 2 * 4입니다.

 

A2를 기준으로 나누어 지기 때문에 j = 1, s = 2, i = 4로

 

matrix[1][0] * matrix[2][1]  * matrix[4][1] = 5 * 2 * 4 = 40

 

 

이렇게 보면 공식이 발견됩니다.

i : 목적지, j : 출발지, s : 합치는 구역(j ≤ s ＜ i), 범위 : j~i

DP[j][i] = DP[i][s] + DP[s+1][j] + matrix[j][0] * matrix[s][1] * matrix[i][1]에서 s의 범위 중 최소 연산 수를 구할 수 있습니다.

 

이제는 어떤 순서로 DP를 구해야하는지 고민을 해보았습니다.

구해야하는 DP값은 DP[1][K]의 값으로써 목적지를 2부터 시작하면 됩니다.

즉 DP[1][2]->DP[2][3] -> DP[1][3] -> DP[3][4] -> DP[2][4] -> DP[1][4] .....이렇게 진행되게 하였습니다.

문제를 해결한 알고리즘의 과정입니다.

1. DP[i][j]의 값을 Integer.MAX_VALUE로 초기화해줍니다.

2. DP[1][2]을 시작으로 DP[1][K]까지 구해줍니다.

3. DP[1][K]을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 이용하여 비용값들을 받고 matrix[] 배열을 초기화해주었습니다.
• 연산 최소의 개수 구하는 matrixMul 함수를 만들었습니다.
• BufferedWriter에 DP[1][K]의 값을을 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• matrixMul는 3중 반복문을 통해서 DP[1][2]부터 DP[1][K]까지의 최소 연산 횟수를 구하였습니다.
• matrixMul는 위에 설명한 알고리즘 대로 DP와 matrix를 이용하여 최소 연산 횟수를 구하였습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	public static int[][] matrix;		//행렬의 크기 저장 배열
	public static int[][] DP = new int[501][501];		//행렬의 곱 최소 연산 수 저장 배열
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
    	StringTokenizer st;
        //----------입력값 저장 및 배열 초기화---------
    	int N = Integer.parseInt(br.readLine());
    	matrix = new int[N+1][2];
    	for(int i=1;i<=N;i++) {
    		st = new StringTokenizer(br.readLine()," ");
    		matrix[i][0] = Integer.parseInt(st.nextToken());
    		matrix[i][1] = Integer.parseInt(st.nextToken());
    	}
    	matrixMul(N);		//함수 실행
    	bw.write(DP[1][N] + "\n");		//결과 BufferedWriter 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    	
    }
    //---------행렬 곱셈의 연산의 수 최고값 구하는 함수--------
    public static void matrixMul(int N) {
    	for(int i=2;i<=N;i++) {		//목적지
    		for(int j=i-1;j>0;j--) {		//출발지
    			DP[j][i] = Integer.MAX_VALUE;
    			for(int s = j;s<i;s++) {		//중간 지점
                		//행렬의 곱셈 연산 수
    				int temp = matrix[j][0] * matrix[s][1] * matrix[i][1];
                   		//최소값 구하기
    				DP[j][i] = Math.min(DP[j][i], DP[j][s] + DP[s+1][i] + temp);
    			}
    		}
    	}
    }
}