[백준] 11049 행렬 곱셈 순서 : C++ 풀이

문제 링크

https://boj.kr/11049

11049번: 행렬 곱셈 순서

주어지는 행렬들의 최적 곱셈을 위한 순서배치인줄 알았는데,
행렬의 순서를 바꾸는게 아니고, 행렬의 계산순서는 그대로 고정이라고 한다....

곱셈 자체의 순서만을 정하는 문제인데, 이걸 몰라서 많이 헤맸다.

그러니까 무슨 말이냐면, 행렬이 2x2 2x4 4x2 이렇게 주어진다면, 2x4 4x2 2x4 이런식으로 순서를 바꿔서 계산할 수 없다는 뜻이다.

따라서 그냥 어느 것을 먼저 곱하느냐의 문제가 된다.

 

처음 접근 시 내 생각

행렬이 5x3 / 3x2 / 2x6 이 주어 졌을 때
만약 마지막에 6x4 를 더한다면 이전 결과의 값에 영향을 끼칠까? => yes..

어떻게? dp[3] x new 가 정답일수도 있고, dp[2] x (2x6 x new)가 정답일 수도 있다. 해당 경우는 2x6 x new의 연산 순서가 결과에 영향을 미치지 않기 때문에 해당 경우의 수밖에없다.


행렬이 5x3 / 3x2 / 2x6 / 6x4 이 주어졌을 때 만약 마지막에 4x8 이 주어진다고 할때
이전 값의 영향을 통해 최적값을 어떻게 구할 수 있을까?
dp[2] x (2x6 x 6x4 x new) 가 된다면, 2x6 / 6x4 / new 세 행렬의 연산의 순서가 영향을 미치게 될 수도 있다.

이에 대한 해결 방안

1. dp에 start/end 포인트의 정보를 메모이제이션하기 (맞았던 발상)

이게 무슨 소리냐면, dp[2][3] 은 두번째 행렬부터 세번째 행렬까지의 곱셈 최적값을 의미한다.
이렇게 되면 시간 복잡도는 어떻게 해결할 수 있으며, 어떻게 전수조사가 될까?

1-1. 시간 복잡도

시간 복잡도는 일단 N개만큼의 행렬이 있다면, N^2개만큼의 최적값을 알아내야한다. 최소 N^2 이 걸린다.

하지만 start / end 까지 생각한다면 N번 더 구해야하기 때문에 아마 N^3이 될거라고 어림짐작했다.

처음 생각한 해법 (잘못된 정답 이지만 부분적으로 올바르다)

- dp[1][1]은 무조건 0

- dp[N][N]도 무조건 0 (할필요 없기 때문에) (N번 반복)

- dp[N-1][N] 은 arr[N-1][0]*arr[N-1][1]*arr[N][1]

for(i=1; i<N-1; ++i)
dp[i][N] for(int j=0; j<i; ++j) 안에서,

 

dp[i][N] = max(dp[i][j] + "new와 뒤에서부터 arr[j]까지 합성한 backSum" + arr[i][0]*arr[j][1]*arr[N][1], dp[i][N])

(여기서 new란 새로 추가되는 N+1번째의 행렬이다.)

backSum 계산은 알아서 뒤에서부터 곱해나가면 된다고 생각했다.

시간 복잡도 : O(N^3)  = 500^3 = 250000*500 = 125/000/000 인데 정확히 N^3은 아닌게, 계단식 계산이라 이것의 1/2 이다.

따라서 1억번 연산은 넘기지 않게 될 것이고, 이것이 해법이라고 생각했다.

반례

하지만 뒤에서부터 합성한 backSum 값을 바탕으로 dp를 구하는 것은 불가능하다.

K가 맨 중간에 있을 때, backSum은 그냥 맨 뒤에서부터 순서대로 곱한 결과만을 찾게 된다. 정확한 해법을 찾기 위해서는, 1부터 K, K+1부터 N까지의 부분 최적해를 먼저 찾아 놓아야합니다.

제대로된 생각

내가 무슨 생각을 못했을까?

기저조건을 제대로 정하지 못했었다. 일단 가장 자명한 조건은 구간이 1인 모든 부분 최적값을 알면, 구간이 2인 모든 부분 최적값을 알 수 있고,

구간이 2인 모든 부분 최적값을 알면, 구간이 3인 모든 부분 최적값을 알 수 있다.

이렇게, 기저조건을 먼저 세우는 방식을 잘못 정했고, 수학적 귀납적을 제대로 활용하지 못했다.

이 기저조건을 바탕으로 제대로 생각하면 이렇게 된다.

for(int len=1; len<N; ++len) // i는 구간의 크기
for(int s=1; s + len <= N; ++s) // s 는 시작점을 의미
for(int k=s; k<=s+len; ++k) // k는 메모한 값을 바탕으로 최적해를 구하기 위한 검색을 위한 중간지점

이제 K 구간으로 나눴다. K 행렬을 빼고 구하는게 아니다. s부터 K 행렬까지의 최적해와 K + 1부터 s + len 까지의 최적해와 곱셈시 필요 계산량을 따지는 것이다.

따라서

 

dp[s][s + len] = min(dp[s][s + len], dp[s][k] + dp[k+1][N] + arr[s][0]*arr[k+1][0]*arr[s + len][1]);

 

이것이 점화식이 된다.... 진짜 어렵다 ㅋㅋㅋ

- 요약

기저 조건 제대로 생각하기. 근거는 수학적 귀납법이 확실히 가능하도록 소급될 수 있는 경우를 기준으로 하기.

DP를 생각한 건 잘했다.

 

소스코드

말로 설명하는건 어려워해서, 소스코드를 봐서라도 이해할 수 있다면 좋겠습니다.

#include<iostream>
#include<algorithm>
using namespace std;

int arr[501][2];
int dp[501][501]; // start - end
const int INF = 2147483647;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int N; cin >> N;
	for (int i = 1; i <= N; ++i) {
		cin >> arr[i][0] >> arr[i][1];
	}

	for (int len = 1; len < N; ++len) {
		for (int s = 1; s + len <= N; ++s) {
			dp[s][s + len] = INF;
			for (int k = s; k <= s + len; ++k) {
				dp[s][s + len] = min(dp[s][s + len], dp[s][k] + dp[k+1][s + len] + arr[s][0] * arr[k + 1][0] * arr[s + len][1]);
			}
		}
	}
	
	cout << dp[1][N];
}