[다이나믹 프로그래밍] 11049번 - 행렬 곱셈 순서

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

(한줄평) 이전에 풀었던 문제와 풀이 방식이 비슷해서 풀 수 있었지만 다음에 다시 풀면 못 풀 것 같기도 한 문제.. 복습이 꼭 필요하다!

유사 문제: 11066

https://hseungyeon.tistory.com/313

[다이나믹 프로그래밍] ★★ 11066번 - 파일 합치기

 

풀이 시간: 60분 이내

1) 문제 해결 아이디어

n개의 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 구하는 문제다.

이 문제의 핵심은 대각선방향으로 각 칸의 값을 구하는 것이다.

 

<점화식>

(i ~ j)를 (i~x), (x+1~j)로 쪼개고 각각의 행렬 연산의 결과를 곱하는 연산 횟수를 더해주는 것이 포인트다.

 

2) 소스코드

import sys
input = sys.stdin.readline

n = int(input())  # 행렬의 개수(1이상 500이하)
# n개의 행렬 크기(r, c)
graph = [list(map(int, input().split())) for _ in range(n)]

# i에서 j까지 행렬을 곱하는 데 필요한 곱셈 연산의 최솟값
d = [[0] * n for _ in range(n)]

# (n-1)번 대각선으로 
for k in range(n-1): 
  for i in range(n-k-1):
    j = i + k + 1
    # 2. 두번째 대각선 이후 경우
    if k != 0:
      # i~x, x+1~j 케이스들의 최소 연산 횟수 중 최솟값 대입
      cnt = [d[i][x] + d[x+1][j] + graph[i][0] * graph[x][1] * graph[j][1] for x in range(i, j)]
      d[i][j] = min(cnt)
    # 1. 첫번째 대각선의 경우
    else:
      # 두 행렬의 곱셈 연산 횟수로 초기화
      d[i][j] = graph[i][0] * graph[i][1] * graph[j][1]

print(d[0][n-1])  # 0~(n-1)번째 행렬을 곱하는 최소 연산 횟수