알고리즘/백준(BOJ)
[백준/C++] 11049번 행렬 곱셈 순서
https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 알고리즘 수업에 나온 내용이 백준 문제에 있길래 풀어보았다. 우선 행과 열 값들을 저장해준다. 그런 다음 삼중 for문(O(n^3)) 을 이용해 값을 구해준다. 행렬곱셈의 순서는 다른 dp 문제들과 동일하다. 바텀 업으로 시작하여 값을 계산하고, 계산된 값을 저장한다. 그리고 그 계산된 값을 이용하여 답을 구하는 것이다. 행렬 곱셈순서를 구하기 위해서는 몇개를 곱할 것인지, 시작점은 ..
