728x90
http://www.acmicpc.net/problem/11049
# 조건
- 크기가 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)
- 항상 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어진다.
# 접근방법
- DP를 이용하여 행렬을 곱하는데 필요한 곱셈의 최소 횟수를 담아준다. - 연쇄 행렬 곱셈 이용
- dp[i][j] 는 matrix[i]에서 matrix[j] 까지 행렬을 곱하는데 필요한 곱셈의 최소 횟수를 뜻한다.
- 즉 i번째 행렬과 j번째 행렬을 곱할 때, 연산이 최소가 되는 횟수
min(ABCD) = min(
dp[ABCD],
dp[A] + dp[BCD] + A[0] A[1] D[1],
dp[AB] + dp[CD] + A[0] B[1] D[1],
dp[ABC] + dp[D] + A[0] C[1] D[1]
) = min(
dp[0][4],
dp[0][0] + dp[0][3] + A[0] A[1] D[1],
dp[0][1] + dp[1][3] + A[0] B[1] D[1],
dp[0][2] + dp[2][3] + A[0] C[1] D[1],
)
- i부터 j까지 곱하는 경우를 생각할 때, 그 사이에 먼저 곱하는 행렬이 존재할 수도, 그렇지 않을 수도 있다.
- 존재하지 않는다면 k는 항상 i과 같거나, j와 같아야 한다.
- 그런데, 존재한다면 어디서 존재하는 지를 알아야 하는데, 이는 불가능하다.
- 따라서 먼저 곱해지는 행렬의 위치를 또다른 변수 k로 놓는다면, 항상 i와 j의 곱하는 연산의 최소값은
- i와 k까지의 연산의 최소값 + k + 1과 j까지의 연산의 최소값이라 할 수 있다.
- 따라서 D[0][3]은 k가 0,1,2가 될 수 있으며, 위의 표처럼 D[0][2]를 채우는 논리만 적용한다면, k가 0,2일때만 D[0][3]의 경우를 구하는 것이므로 k의 모든 경우에 대해 D[0][3]의 값을 갱신할 수 없다.
- 이 경우 k가 1인 경우가 최소이며 D[0][3]은 231이 아니라 184이다.
pypy 제출
N = int(input())
matrix = [list(map(int, input().split())) for _ in range(N)]
# 곱셈의 최소 횟수 행렬
dp = [[0]*N for _ in range(N)]
for diagonal in range(1, N): # dp[i][i]는 자기 자신의 행렬이기 때문에 값이 0
for i in range(0, N-diagonal): # 대각선의 우측 한 칸씩 이동
j = i + diagonal # 현재 대각선에서 몇 번째 원소인지
# 차이가 1밖에 나지 않는 칸
if diagonal == 1:
dp[i][j] = matrix[i][0] * matrix[j][0] * matrix[j][1]
continue
dp[i][j] = float('inf')
# 각 부분행렬의 곱셈 횟수 + 두 행렬의 곱셈 횟수
for k in range(i, j): # k값으로 최적분할 찾기
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + matrix[i][0] * matrix[k][1] * matrix[j][1])
print(dp[0][N-1])
다른 분 코드 - python 제출
n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
arr = [a for a, _ in arr] + [arr[-1][1]]
dp = [[0] * n for _ in range(n)]
for step in range(1,n):
for loc in range(n-step):
end = loc + step
mul = arr[loc] * arr[end+1]
minimum = min(yk + xk + sz * mul for yk, xk, sz in zip(dp[loc][loc:end], dp[end][loc+1:end+1], arr[loc+1:end+1]))
dp[loc][end] = dp[end][loc] = minimum
print(dp[0][-1])
728x90
'ALGORITHM > DP(동적 계획법)' 카테고리의 다른 글
[백준 14002번] 파이썬 - 가장 긴 증가하는 부분수열 4 (0) | 2023.03.18 |
---|---|
[백준 14501번] 파이썬 - 퇴사 (0) | 2023.03.12 |
[백준 2098번] 파이썬 - 외판원 순회 (0) | 2023.02.21 |
[백준 7579번] 파이썬(python) - 앱 (1) | 2023.01.28 |
[백준 9252번] 파이썬 - LCS2 (0) | 2023.01.24 |