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

🔺 문제

11049번: 행렬 곱셈 순서

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;       // 행렬 개수
    static Matrix[] M;  // 행렬 저장 클래스 배열
    static int[][] D;   // i~j번째 행렬까지 최소 연산 횟수 저장
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        
        N = Integer.parseInt(st.nextToken());
        M = new Matrix[N + 1];
        D = new int[N + 1][N + 1];
        
        // 테이블 초기화
        for(int i = 0 ; i < D.length ; i++) {
            for(int j = 0 ; j < D[i].length ; j++) {
                D[i][j] = -1;
            }
        }
        
        // 행렬 입력받기
        for(int i = 1 ; i <= N ; i++) {
            st = new StringTokenizer(br.readLine()," ");
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            M[i] = new Matrix(r, c);
        }
 
        System.out.println(execute(1, N));
    }
    
    // Top-Down 방식 점화식 구현
    static int execute(int s, int e) {
        int result = Integer.MAX_VALUE;
        
        // 계산했던 부분은 다시 계산 X (메모이제이션)
        if(D[s][e] != -1)
            return D[s][e];
        // 행렬 1개일 때
        if(s == e)
            return 0;
        // 행렬 2개일 때 (앞 행렬 row * 뒤 행렬 row * 뒤 행렬 col)
        if(s + 1 == e)
            return M[s].r * M[s].c * M[e].c;
            
        // 행렬이 3개 이상일 때, 재귀 형태 (Top-Down)
        for(int i = s ; i < e ; i++)
            result = Math.min(result, execute(s, i) + execute(i + 1, e) + M[s].r * M[i].c * M[e].c);
        return D[s][e] = result;
    }
    
    // 행렬 정보 저장용 클래스
    static class Matrix {
        private int r;
        private int c;
        
        Matrix(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}

✅ 해결 아이디어
✔ DP (Top-Down 방식)
- D[ i ][ j ] : i ~ j번째 행렬까지 최소 연산 횟수 저장

 

행렬 정보 저장용 클래스를 따로 만들었다.

---

🔺 다른 풀이들

- 행렬 정보 저장용 클래스를 따로 만드는 대신 2차원 배열을 사용하셨다. (재귀, 반복문 코드 둘다 볼 수 있음)

백준 11049 행렬 곱셈 순서 Java

 

- 2차원 배열 사용

https://www.acmicpc.net/source/26585402

로그인

 

 

 

- 재귀) 깔끔 풀이 그 잡채

[java] 백준 11049 (행렬 곱셈 순서) Gold 3

 

- 반복문) 깔끔 코드 그 잡채 (3중 for문) => 복습용!

[BaekJoon] 백준 11049번 행렬 곱셈 순서(Java)

---

💬 느낀 점

아이디어 생각하기까지가 어렵당...

 

 

 

1회독	2회독	3회독	4회독	5회독
V	7/10

 

(+7/10 2회독)

흐아아.... 투 포인터로 풀다가 시간 초과 떠서 우짜지..하고

이전 코드 보고 코드 작성했다..ㅠ

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static Matrix[] M;
    static int[][] D;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        M = new Matrix[N + 1];
        
        // dp 배열 초기화
        D = new int[N + 1][N + 1];
        for (int i = 0; i < D.length ; i++) {
            for(int j = 0 ; j < D[i].length ; j++) {
                D[i][j] = -1;
            }
        }
        
        for(int i = 1 ; i <= N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            M[i] = new Matrix(r, c);
        }
        
        System.out.println(solve(1, N));
    }
    
    private static int solve(int s, int e) {
        int result = Integer.MAX_VALUE;
        
        if(D[s][e] != -1)
            return D[s][e];
        if(s == e)
            return 0;
        if(s + 1 == e)
            return M[s].r * M[s].c * M[e].c;
            
        for(int i = s ; i < e ; i++) {
            result = Math.min(result, solve(s, i) + solve(i + 1, e) + M[s].r * M[i].c * M[e].c);
        }
        return D[s][e] = result;
    }
    
    static class Matrix {
        int r, c;
        
        Matrix(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}
 

 

 

---

(참고)

✔ Do it 알고리즘 코딩테스트 자바편