WonYong-Jang
commented
5 years ago 행렬 곱셈 순서 (백준)
for(int i=0; i<N; i++)
{
st = new StringTokenizer(br.readLine());
num1 = Integer.parseInt(st.nextToken());
num2 = Integer.parseInt(st.nextToken());
d[i] = num1;
d[i+1] = num2;
}
for(int diagonal=0; diagonal < N; diagonal++) // 대각선
{
for(int i=1; i<= N - diagonal; i++) // (1,1) (2,2) (3,3) (1,2) (2,3) (1,3) 순서
{
int j = i + diagonal;
if(i == j) {
dp[i][j] = 0;
continue;
}
}
dp[i][j] = INF;
for(int k= i; k <= j-1; k++) //dp[1][4] ==> (1,1)(2,3)/ (1,2)(3,3)/ (1,3)(4,4) 순으로 검사
{
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + (d[i-1]*d[k]*d[j]));
}
}
System.out.println(dp[1][N]);
연쇄 행렬 최소 곱셈 알고리즘
두개 이상의 행렬을 곱할 때, 최소 곱셈 횟수를 구하는 문제
예를들어 설명하면, 행렬 A,B,C,D 4개가 존재한다. 각각 행렬의 차수는 20x1, 1x30, 30x10, 10x10이라고 한다. 4개의 행렬은 여러가지 방법으로 곱할 수 있지만, 다음 4개의 경우에 대하여 생각해볼때, 곱셈 횟수를 비교하면 아래와 같다.
((AB)C)D) = (20130) + (203010) + (201010) = 8,600 A(B(CD)) = (301010) + (13010) + (20110) = 3,500 (AB)(CD) = (20130) + (301010) + (203010) = 9,600 (A((BC)D) = (13010) + (11010) + (20110) = 600
위와 같이 곱셈을 하는 순서에 따라 600~9600번의 곱셈 횟수가 나오게 되는데, 그 중 최소 곱셈 횟수는 600번이다.
점화식
풀이
위 관계식을 아래의 행렬로 하나씩 예를 들어보자. A(20x1),B(1x30),C(30x10),D(10x10) 일때, d0=20, d1=1, d2=30, d3=10, d4=10
M[1][2] (행렬 A~B까지의 곱의 횟수) (1<=k<=1) = minimum(M[1][k] + M[k+1][2] + d0dkd2 = M[1][1] + M[2][2] + d0d1d2 = 0 + 0 + 20130 = 600
M[2][3](행렬 B~C까지의 곱의 횟수) (2<=k<=2) = minimum(M[2][k] + M[k+1][3] + d1dkd3) = M[2][2] + M[3][3] + d1d2d3 = 0+0+13010 = 300
M[1][3](행렬 A~C까지의 곱의 횟수)(1<=k<=2) = minimum(M[1][k] + M[k+1][3] +d0dkd2 = minimum(M[1][1] + M[2][3] + d0d1d3, M[1][2] + M[3][3] + d0d2d3) = minimum(0 + 300+20110, 600+0+203010) = minimum(500, 6600) = 500
행렬 A~D까지의 곱의 횟수 (M[1][4])는 M[1][4] = minimum( M[1][1] + M[2][4] + d0d1d4, M[1][2] + M[3][4] + d0d2d4, M[1][3] + M[4][4] + d0d3d4) M[1][4]를 구하려면 M[1][1]~M[1][4]의 값이 필요하고,(구하려는 값의 테이블 좌측값) M[2][4]~M[4][4]의 값이 필요하고,(구하려는 값의 테이블 아랫값)
M[i][j]의 값은, 대각선을 하나씩 증가시키며 아래와 같이 구할 수 있다.
참고링크 :
http://huiyu.tistory.com/entry/DP-%EC%97%B0%EC%87%84%ED%96%89%EB%A0%AC-%EC%B5%9C%EC%86%8C%EA%B3%B1%EC%85%88-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98