문제 바로가기
문제:
크기가 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) 항상 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어진다.
출력:
첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같다.
2차원 dp로 해야하는것과
3부분으로 나눠서 계산하는거 까지는혼자 이끌어냈다.
하지만 코드로는 표현하지 못했다.
내가 공부하는데 도움을 받은 사람들의 링크를 남겨 같이 공유했으면한다.
[python] 백준 11049 :: 행렬 곱셈 순서 (DP)
[행렬 곱셈 순서] # 문제 크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게
e-juhee.tistory.com
[DP] 백준 - 행렬 곱셈 순서 11049번
행렬 곱셈 순서 11049번 모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값을 구하는 프로그램을 작성하시오. 예시 : ABCD의 행렬의 최솟값을 구하기 위해서는 A(BCD) (AB)(CD) (ABC)D ABCD중 최솟값을
velog.io
https://www.youtube.com/watch?v=Tdl6VP4bS90
내 풀이:
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
n = int(input())
graph = [list(map(int, sys.stdin.readline().rstrip().split(" "))) for _ in range(n)]
dp = [[0] * n for _ in range(n)]
for i in range(1, n):
for j in range(n - i):
x = i + j
dp[j][x] = 2 ** 32
for k in range(j, x):
dp[j][x] = min(dp[j][x], dp[j][k] + dp[k + 1][x] + graph[j][0] * graph[k][1] * graph[x][1])
print(dp[0][-1])
마지막 포문 부분이 제일 중요한 것 같다.
그냥 외워버릴까.?
4개 짜리로 따지면
| a | b | c | result |
| d | |||
| e | |||
| f |
reulst는
왼쪽 : a + 가운데 : d + 오른쪽 a*b*e
왼쪽 : b + 가운데 : e + 오른쪽 a*c*e
왼쪽 : c + 가운데 : f + 오른쪽 a*d*e
오른쪽 부분이 어떻게 저렇게 나오냐? 할 수 있는데
만약 ABCDEFGH 가 있다고 하자
그럼 이걸 2등분한다 대충 ABCDE FGH 이렇게
그리고 곱셈으로 나타내면 예를들어
A = a,b B = b,c = 이 둘의 합은 a*b*c 이고 나오는 행렬은 a*b 이다 이거를 저기에 대입하면
| A | B | C | D | E | F | G | H |
| a | b | c | d | e | f | g | h |
| b | c | d | e | f | g | h | i |
이렇게 r, c 를 가지게되는데
다 제끼게 되면 결국에 나오는 행렬은 a*i 행렬인 것이다.
그래서 ABCD를 구하기전에 AB, CD, ABC,BCD 등 행렬의 최솟값들을 다 구한후 계산하면 된다.
진짜 미친놈이다.
이해한거 같은데 내일 다시 풀어봐야겠다
댓글