백준 110491 11049. 행렬 곱셈 순서 (Python) 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 풀이 2차원 dp를 활용하여 구할 수 있다. 2차원 dp는 다음을 의미한다. 위의 예제는 dp[2][5]를 구하는 과정 중 하나의 예를 나타낸다. dp[2][5]를 구하기 위해서는 다음과 같은 경우를 모두 탐색해야 한다. dp[2][2] + dp[3][5] + 곱셈 연산 dp[2][3] + dp[4][5] + 곱셈 연산 dp[2][4] + dp[5][5] + 곱셈 연산 이 중 최솟값이 dp[2][5]에 기록된다. 이를 구하는 점화식은 다음과 같다. f.. 2022. 2. 23. 이전 1 다음
