BOJ 11049

11066번과 동일한 문제이다. 허나 여느 DP 문제가 그렇듯 직접 풀어봐야 패턴 파악 가능

Input

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

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

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

import sys
input = sys.stdin.readline
n = int(input())
s = [list(map(int, input().split())) for _ in range(n)]

DP

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

• 작은 단위부터 곱해나가야 하므로 gap 반복문 먼저 시행

  for gap in range(1, n):

• 이후 처음부터 곱해나가야 하므로 start 반복문 시행

  for start in range(n-1):

• end 범위 지정

  end = start + gap
    
  if end >= n: break

• start 부터 gap 만큼 진행하며 dp값 갱신

  • dp를 0으로 초기화 시켰으므로 주어진 조건에 따라 최대값으로 세팅하고 갱신

  dp[start][end] = 2 ** 31
  for g in range(gap):
    dp[start][end] = min(dp[start][end], dp[start][start+g] + dp[start+g+1][end] + s[start][0]*s[start+g][1]*s[end][1])

Output

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

print(dp[0][-1])