64. 백준 : 행렬 곱셈 순서 (지금까지 한 거 중에 제일 어려운 듯)

 

행렬 여러 개가 주어진다.

ABC가 있을 경우에 (AB)C 에서 연산하는 수와 A(BC) 연산 수가 다르다.

연산 횟수를 가장 작은 값으로 해서 모든 행렬을 곱해라

 

---

이번 문제는 감이 너무 안 오고 오래 걸려서 여러 풀이들을 참고했다.

 

우선 문제 예시처럼 A = 5*3 , B = 3*2 , C = 2*6 로 생각해보자.

- (AB)C = 5*3*2 + 5*2*6 = 30+60 = 90

- A(BC) = 5*3*6 + 3*2*6 = 90+36 = 126

 

음,, 이 예제는 간단하다만 ABCD 처럼 1개만 추가되어도 경우의 수가 매우 다양해진다.

D = 6*7

- (AB)(CD)

- (ABC)D

- A(BC)D

- A(BCD)

...

이런 경우에는 AB, AC, AD 각각 가는 거리의 최소값을 저장해두고 쓰면 편할 것 같다.

만약 AB,BC,CD 이렇게 곱하는 경우에 A-C까지 행렬을 만드는 최소값을 알고 있다면

AC최소값 + 5*3*7 (5*3*7은 A의 행렬과 D의 행렬을 합칠 때 발생하는 연산 수) 로 AC 까지의 연산이 필요 없어진다.

DP가 적당하겠다.

 

📌구상

 

우선 정해야 하는 것들이 있다.

1) 몇 개를 계산할지

 ➡️ 한 번에 다 구하는 게 아니기 때문에, AB, BC, CD 각각 연산의 최솟값( 두 개라 뭐 나올 것도 없음)

       > 그 다음 회차에는 ABC (= min((AB)C , A(BC)) , BCD(= min((BC)D , B(CD)) 

       > 그 다음 회차에는 ABCD ...

 

그럼 이걸 하려고 할 때 필요한 건?

2) 어디서부터 어디까지 계산할지

 ➡️ i,j 를 정해두자. i부터 시작한다면 j는 i+cnt 까지 계산하면 되겠다.

 

3) 어디에서 자를건지

i,j 사이에서 k를 정해서 잘라주자.

 

4) 점화식

dp[i][j] = min(dp[i][j] , dp[i][k] + dp[k+1][j] + mat[i][0]*mat[i][1]*mat[j][1])

점화식 설명 :

1) i ~k 까지 저장된 값을 가져온다.  

2) k+1 ~ j까지 저장된 값을 더한다.

 = 현재 주어진 최솟값을 기반으로 구성

 + 행렬을 합칠 때 필요한 연산 수를 더한다.

 

행렬 6개를 합치기 위해서는, 저 연산들 중에서 가장 작은 값을 취해야 한다.

ABCDEF가 있다고 한다면 (각각 최솟값은 이미 구해져서 칸이 채워져있다고 가정)

- 빨간색 : (AB) (CDEF) 

- 노란색 : (ABC) (CDE) 

 

이 때 (AB)or(ABC) 와 (CDEF)or(CDE) 를 합칠 때 필요한 연산이 있어야 한다.

 

점화식은 다음과 같다.

 

 

---

지금까지 푼 문제 중에 제일 어렵다

사실 dp 테크닉이 어렵다기보다는 행렬에 대해 복습하는 게 빡셌다..

같이 대회 나가신 분이 말씀해주신 것 같이 수학을 공부하지말고 DP 문제를 많이 접해보자.