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

난이도: 골드 III

문제 링크: https://www.acmicpc.net/problem/11049

11049번: 행렬 곱셈 순서

백준 11049번 문제 행렬 곱셈 순서

 

제가 자신없어 하는 편인 DP를 이용하는 문제입니다.

2차원 배열 dp[i][j]를 만드는데, 이때 dp[i][j]는 행렬 i에서 j까지 곱했을 때의 최소 곱연산 횟수라고 정의합니다.

 

맨 처음에는 배열 matrix에, matrix 1번부터 n번까지 각각의 row와 column의 길이를 입력받습니다 (저는 pair를 이용함(.

다음으로, 주어진 모든 matrix에 대해, 인접한 (다음 순서) matrix와의 곱셈 연산의 수를 구하여 dp 배열에 넣어 줍니다.

이 다음부터가 핵심입니다.

변수 m은 j - i를 의미합니다. 따라서 맨 바깥 loop에서 m을 하나씩 증가시키며, m <= n이 됩니다.

i = j - m인데, m <= n이므로, i <= n-m이 됩니다. 따라서 그 다음 loop에서 1 <= i <= n-m의 구간을 가집니다.

j = i + m으로 구할 수 있습니다.

다음으로, k는 i와 j 사이의 중간지점을 의미합니다. i <= k < j이며, dp의 값을 갱신하는 역할을 합니다.

 

점화식은 다음과 같습니다:

result = dp[i][k] + dp[k+1][j] + (matrix[i].first * matrix[k].second * matrix[j].second).

즉 i와 j 사이의 k를 거쳐서 행렬 곱의 곱연산 수를 구할 때, (앞에서 구한) 1번부터 k번까지의 최소곱 + (k+1)번부터 j번까지의 최소곱 + (1번부터 j번까지의 k를 거친 최소곱)이 됩니다.

이 값이 기존 dp[i][j]보다 작거나, dp[i][j]에 아무런 값이 없는 경우 이 값을 dp[i][j]에 적게 됩니다.

 

최종적으로 dp[1][n]에는 matrix 1번부터 n번까지의 최소 곱연산 횟수가 됩니다.

 

코드로 나타내면 다음과 같습니다.

 

 

DP 문제의 경우, 제가 점화식을 생각해내는 것에 어려움을 느껴서 다음과 같은 글을 참고하였습니다.

• https://justicehui.github.io/ps/2018/10/28/BOJ11049/
• https://t-anb.tistory.com/10
• https://guccin.tistory.com/86

DP 문제를 더 집중적으로 풀어 볼 필요성을 느낍니다 ㅎㅎ;

 

채점 결과