[PYTHON] 백준 11049 - 행렬 곱셈 순서

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

성능 요약

메모리: 117556 KB, 시간: 884 ms

분류

다이나믹 프로그래밍

문제 설명

크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다.

예를 들어, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해보자.

• AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 5×3×2 + 5×2×6 = 30 + 60 = 90번이다.
• BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는 3×2×6 + 5×3×6 = 36 + 90 = 126번이다.

같은 곱셈이지만, 곱셈을 하는 순서에 따라서 곱셈 연산의 수가 달라진다.

행렬 N개의 크기가 주어졌을 때, 모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값을 구하는 프로그램을 작성하시오. 입력으로 주어진 행렬의 순서를 바꾸면 안 된다.

입력

첫째 줄에 행렬의 개수 N(1 ≤ N ≤ 500)이 주어진다.

둘째 줄부터 N개 줄에는 행렬의 크기 r과 c가 주어진다. (1 ≤ r, c ≤ 500)

항상 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어진다.

출력

첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같다.

---

아이디어, 문제풀이

• dp를 백터라고 생각하고 풀이해야 한다.
• 예를들어, dp[1][3] 은, 1에서 3으로 가는 최소비용 이라고 생각할 수 있다.

---

TROUBLE SHOOTING

• 일단 아이디어에 쓰여있는대로 문제 풀이를 진행했다.

  def fun(n, graph):
  
      for i in range(n):
          for j in range(n):
  
              if i == j:
                  dp[i][j] = 0
              
              if i+1 == j:
                  dp[i][j] = graph[i][0] * graph[i][1] * graph[j][1]
  
              else:
                  dp[i][j] = float('inf')
                  for k in range(i, j):
                      dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + graph[i][0] * graph[k][1] * graph[j][1])
  
      return dp

  내가 이 문제를 3시간 정도 붙잡고 여러 그림을 그리며 풀었는데, 결론적으로는 for문이 틀렸다. 나는 일단 전체를 탐색한다, 라는 생각으로 문제에 접근했는데, 백준 예제 답은 제대로 나왔지만, 문제를 해결할 순 없었다. 관련 gpt 대답을 함께 첨부한다! 코드를 살펴보면, 이전 코드에서 틀린 부분은 for 문을 사용하는 방식입니다. 이전 코드에서는 for i in range(n)와 for j in range(n)을 사용하여 각 행렬 쌍에 대해 작업을 수행했습니다. 이 방식은 문제를 해결하는 데 필요한 모든 경우를 고려하지 않습니다. 수정된 코드에서는 for l in range(1, n)를 사용하여 체인 길이를 기반으로 반복합니다. 체인 길이를 기반으로 반복하면 문제를 해결하는 데 필요한 모든 행렬 쌍을 고려할 수 있습니다. 즉, 이전 코드는 구간 길이에 따라 모든 경우를 고려하지 않았으므로 틀린 결과를 얻었습니다. 수정된 코드는 다음과 같이 for문을 구성합니다.

  1. 첫 번째 for문은 체인 길이를 기반으로 반복합니다.

  2. 두 번째 for문은 시작 행렬을 기반으로 반복합니다.

  3. 세 번째 for문은 행렬을 분할하는 지점을 기반으로 반복합니다.

     이렇게 구성된 3중 반복문을 사용하면 문제를 해결하는 데 필요한 모든 경우를 고려하여 최소 곱셈 횟수를 찾을 수 있습니다.

     요약해서 이야기하면, 모든 행렬쌍을 고려하지 않고, 내가 원하는 행렬쌍만 계산했다는 점인데… 역시나 쉽지않은 이야기다. A,B,C,D 에서 어떤 두개의 행렬이 먼저 연산될지 모른다. 모든 chain을 고려해야한다. 와 같은 이야기로 해석하면 이해하기 편할것 같다.

• 아래 코드도 구현하기에 난이도가 너무 높았던것 같다.

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

  어떻게 생각해 내는걸까… 나중에 더 익숙해지면 쉬워질까? 하루종일 고민한다면 될것 같다고도 생각하는데… 잘은 모르겠다. 당장은 저 점화식을 적용해 문제를 풀어낼 수 있는지에 집중하는게 나을것 같다.
  

---

코드

#https://www.acmicpc.net/problem/11049
#행렬 곱셈 순서
#11049

import sys

n = int(input())

graph = []
for _ in range(n):
    a, b = map(int, input().split())
    graph.append([a, b])

dp = [[0] * n for _ in range(n)]

for length in range(1, n):  # 행렬 곱셈 길이
    for i in range(n - length):  # 시작 행렬 인덱스
        j = i + length  # 끝 행렬 인덱스
        dp[i][j] = float('inf')
        for k in range(i, j):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + graph[i][0] * graph[k][1] * graph[j][1])

print(dp[0][n-1])