2018. 3. 20. 16:11, 알고리즘/BOJ
https://www.acmicpc.net/problem/11049
전형적인 DP 문제입니다. D[i][j]를 matrix[i:j]를 곱할 때 필요한 최소 연산 수라고 할 때, sep = i+1~j-1에 대해 D[i][j] = min(D[i][sep]+D[sep][j]+matrix[i]의 row*matrix[sep]의 row*matrix[j]의 col) 이 됩니다.
O(N^3)에 해결이 가능합니다.
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 1943번: 동전 분배 (2) | 2018.03.24 |
---|---|
[BOJ] 6986번: 절사평균 (0) | 2018.03.22 |
[BOJ] 10835번: 카드게임 (4) | 2018.03.20 |
[BOJ] 1509번: 팰린드롬 분할 (0) | 2018.03.20 |
[BOJ] 5557번: 1학년 (0) | 2018.03.20 |
[BOJ] 1036번: 36진수 (0) | 2018.03.16 |
Comments