다이나믹 프로그래밍
- 작은 문제의 답이 큰 문제의 답을 계산할 때 활용
- 두 가지 풀이 방법이 있음
- 상향식 풀이: for 문 돌면서 작은 문제부터 답을 계산
- 하향식 풀이: 분할정복 형태로 문제를 쪼개면서 재귀로 구현
- 점화식을 세울 때
- 작은 문제의 답부터 생각해볼것
- 큰 문제의 답을 작은 문제 답으로 계산할 수 있는지 생각해볼것
- 메모이제이션
- 초기값 설정을 잘 해야 함 (메모리를 한칸 더 크게 잡는다던가)
노트
1) 지금 단계의 해답 = 부분문제의 해답 + 추가 계산
풀이
1) 분할정복
- 행렬을 좌 우 행렬로 나누고 각각 재귀
- 좌 우를 나누는 모든 경우에 대해 테스트
2) 행렬 곱 횟수 = 부분행렬 곱 횟수 + 현재 행렬의 곱 횟수
def solve(sidx, eidx)
...
count = solve(sidx, i) + solve(i+1, eidx)
count += data[sidx][0] * data[i][1] * data[eidx][1]
dp[sidx][eidx] = min(dp[sidx][eidx], count )
문제점
코드
"""
DP
dp[sidx][eidx] = min(dp[sidx][i] + dp[i][eidx]) + sidx ~ i 행렬 x i ~ eidx 행
"""
import sys
# sys.setrecursionlimit(10**6)
def solve(sidx, eidx):
# print(sidx, eidx)
# 가장 밑에 있는 재귀 처리
if sidx == eidx:
return 0
# 가장 밑에 있는 재귀 처리
if sidx + 1 == eidx:
dp[sidx][eidx] = data[sidx][0] * data[sidx][1] * data[eidx][1]
return dp[sidx][eidx]
# 메모이제이션
if dp[sidx][eidx] != 0:
return dp[sidx][eidx]
dp[sidx][eidx] = sys.maxsize
for i in range(sidx, eidx):
# 분할정복
count = solve(sidx, i) + solve(i+1, eidx)
# 현재단계에서 필요한 추가 연산
count += data[sidx][0] * data[i][1] * data[eidx][1]
# 최솟값 계산
dp[sidx][eidx] = min(dp[sidx][eidx], count )
return dp[sidx][eidx]
sys.stdin = open('./11049.txt')
n = int(input())
dp = [[0 for _ in range(n)] for _ in range(n)]
data = []
for i in range(n):
line = list(map(int, input().split()))
data.append(line)
out = solve(0, n-1)
print(out)
