[백준] 11049번 : 행렬 곱셈 순서 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

https://www.acmicpc.net/problem/11049

 

1. 문제 설명

반응형

2. 풀이과정

해당 문제는 백준 11066번 : 파일 합지기 문제와 풀이 방법이 유사하다.

해당 문제 역시 행렬을 모두 곱하는 연산을 수행할 때 필요한 곱셈 연산의 수가 최소가 되는 값을 구하는 문제이다.

행렬을 하나하나 곱하면서 최종 결과가 최적일 때, 바로 이전의 결과들 또한 최적이어야 하는 문제, 즉 이전 11066번 문제와 동일하므로 다이나믹 프로그래밍 알고리즘을 활용하여 문제를 해결해야 한다.

 

이번 문제는 단순히 덧셈 연산만 존재하는 것이 아니라 행렬의 곱셈 연산으로 인해 곱셈 연산이 추가되었다.

추가된 곱셈 연산을 어떻게 수행해야 하는지를 찾는 것이 중요하다.

11066번 문제와 마찬가지로 곱셈할 행렬의 개수를 늘려가며 바로 전 2개의 행렬을 곱하는 연산을 생각해 본다.

중간 행렬을 바꿔가며 해당 행렬 곱에서 최적의 경우를 찾는다.

해당 문제 역시 이전 행렬의 곱셈 연산의 수를 더하는 것 이외에, 마지막 두 행렬의 곱셈 연산의 수를 최종적으로 더해줘야 한다.

마지막 두 행렬의 곱셈 연산은 앞 행렬의 행과 열에 뒷 행렬의 열을 모두 곱하면 된다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 행렬의 개수를 입력받는다. N = int(sys.stdin.readline())
3. 행렬의 곱셈 연산의 수를 계산할 때 사용할 값을 저장할 리스트를 생성한다. matrix = []
4. 행렬의 개수만큼 반복하며 for _ in range(N)
   1. 행렬의 행과 열의 크기를 입력받는다. r, c = map(int, sys.stdin.readline().split())
   2. 행렬의 행의 크기를 리스트에 추가한다. matrix.append(r)
5. 마지막 행렬의 열의 크기를 리스트에 추가한다. matrix.append(c)
6. 행렬의 곱셈 연산의 수를 저장할 2차원 배열을 생성하고 초기화한다. dp = list([0] * (N + 1) for _ in range(N + 1))
7. 시작 행렬과 마지막 행렬의 차이를 1부터 행렬 개수 전까지 반복하며 행렬의 개수를 점차 늘려 행렬을 곱해준다. for cnt in range(1, N)
   1. 곱할 행렬의 시작 행렬은 1번부터 행렬 번호 차이에 따라 반복하며 for start in range(1, N - cnt + 1)
      1. 마지막 행렬은 시작 행렬에서 행렬 번호 차이만큼 뒤에 있는 행렬을 의미한다. end = start + cnt
      2. 해당 경우를 저장할 배열의 값에 최댓값을 저장해 준다. dp[start][end] = sys.maxsize
      3. 행렬의 중간 위치를 시작 행렬부터 마지막 행렬 전까지로 변경하며 각 2개의 행렬을 곱할 때 2개의 행렬의 곱셈 연산의 수의 합과 마지막 2개의 행렬을 곱할 때 연산의 수를 더해 모든 경우 중 최솟값을 저장한다. for mid in range(start, end): dp[start][end] = min(dp[start][end], dp[start][mid] + dp[mid + 1][end] + matrix[start - 1] * matrix[mid] * matrix[end])
8. 최종적으로 1번부터 마지막 행렬까지 곱했을 때 최소 곱셈 연산의 수를 출력한다. print(dp[1][N])

3. 소스코드

import sys

N = int(sys.stdin.readline())

matrix = []
for _ in range(N):
    r, c = map(int, sys.stdin.readline().split())
    matrix.append(r)
matrix.append(c)

dp = list([0] * (N + 1) for _ in range(N + 1))
for cnt in range(1, N):
    for start in range(1, N - cnt + 1):
        end = start + cnt
					
        dp[start][end] = sys.maxsize
        for mid in range(start, end):
            dp[start][end] = min(dp[start][end], dp[start][mid] + dp[mid + 1][end] + matrix[start - 1] * matrix[mid] * matrix[end])

print(dp[1][N])