[백준] 11049 행렬곱셈순서

문제보기

Top Down 사용하면 좋을 때가 언제일까 곰곰히 생각중

뭔가 순차적으로 점화식을 쌓긴 좀 힘들것 같고, 그리디? 당근 안될거 같을 때

뭔가 한 경우를 결정짓기 위해 해야할 연산이 좀 많아보일때??

그럴때 탑다운으로 메모이제이션하면서 해주면 금방 되는것 같다

이 문제는 파일합치기문제와 매우 유사한데,

i번째부터 j번째까지 기준으로 나온 최솟값을 구하려면

괄호가 (i, i+1) (i+2, j) 인 경우랑, (i, i+2) (i+3, j)인 경우랑 … (i, j-2) (j-1, j) 인 경우를 모두 계산해서 이 중 젤 작은 넘을 골라야 하는 것이다

그래서 탑다운으로가면 좋다

import java.util.*;
import java.io.*;
// 행, 열을 저장할 클래스 
class Mat{
  int r;
  int c;
  Mat(int r, int c){
    this.r = r;
    this.c = c;
  }
}
public class Main{
  static int[][] d;
  static Mat[] a;
  
  static int go(int x, int y){
    // 둘이 같다면 연산할 의미가 없으므로 0반환 
    if(x == y){
      return 0;
    }
    // 메모된 값이 있다면 꺼내 쓴다
    if(d[x][y] != -1){
      return d[x][y];
    }
		
    // 대충 큰값으로 초기화
    int ans = 2000000000;
    // 이게 앞서 설명한 괄호 어떻게 치느냐에 따른 최솟값을 구하는 방법이다.
    for(int i = x ; i < y ; i++ ){
      // ans = min(ans, 비교대상) 의 방식은 for문 돌아갈 때 참 쓰기 좋다
      // 뒤에  a[x].r*a[i].c*a[y].c 는 뭐냐면 어차피 쭉 압축되었을 때
      // 행렬 곱셈 연산 횟수가 이걸로 결정되기 때문이다 
      // 모르겠다면 대충 	5 3 / 3 2 / 2 6 을 각각 괄호 쳐가면서 해보자
      ans = Math.min(ans, go(x, i) + go(i+1, y) + a[x].r*a[i].c*a[y].c);
    }
    d[x][y] = ans; // 메모이제이션 
    return ans; // 날 부른 go에게 결과값을 전달해준다 
  }

  public static void main(String []args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    a = new Mat[n];
    for(int i = 0 ; i < n ; i++ ){
      StringTokenizer st = new StringTokenizer(br.readLine());
      a[i] = new Mat(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
    }

    d = new int[n][n];
    for(int i = 0 ; i < n ; i++ ){
      Arrays.fill(d[i], -1);
    }
    System.out.println(go(0, n-1));

  }
}