문제 설명 및 제한사항
아이디어 및 해결 방법
코드
def numop(r1, c1, r2, c2):
return r1 * c1 * c2
def solution(matrix_sizes):
M = matrix_sizes
n = len(M)
A = [[0] * n for _ in range(n)]
# DP matrix의 i < j인 부분만 값을 채우는데,
# d = j-i 의 값이 1, 2, ..., n-1 인 쌍의 순서대로
# 값을 채웁니다.
for d in range(1, n):
for i in range(n):
j = i + d
if j >= n:
break
if d == 1:
A[i][j] = numop(M[i][0], M[i][1], M[j][0], M[j][1])
else:
candidates = []
for k in range(d):
# (1) i~i+k번째 행렬까지 최적으로 곱할 때의 연산 수와,
a = A[i][i+k]
# (2) i+k+1~j번째 행렬까지 최적으로 곱할 떄의 연산 수와,
b = A[i+k+1][j]
# (3) (i~i+k)번째 행렬곱과 (i+k+1~j)번째 행렬곱의 연산 수를
c = numop(M[i][0], M[i+k][1], M[i+k+1][0], M[j][1])
# 더한 값들을 비교해야 합니다. 후보 리스트에 넣고 최솟값을 구합시다.
candidates.append(a+b+c)
# A[i][j] 는 후보 리스트 중 최솟값입니다.
A[i][j] = min(candidates)
return A[0][n-1]
Python
복사
출처
프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges