[BAEKJOON] 11066 파일 합치기

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int for_count, n, input; scanf("%d", &for_count); while (for_count--) { vector<long long>sum(501); vector<vector<long long>>DP(501, vector<long long>(501)); scanf("%d", &n); for (int x = 1; x <= n; x++) { scanf("%d", &input); sum[x] = sum[x - 1] + input; } int y; for (int diagonal = 0; diagonal <= n; diagonal++) { for (int x = 1; x + diagonal <= n; x++) { y = x + diagonal; if (x == y) { DP[x][y] = 0; continue; } DP[x][y] = 2e9; for (int mid = x; mid < y; mid++) DP[x][y] = min(DP[x][y], DP[x][mid] + DP[mid + 1][y] + (sum[y] - sum[x - 1])); } } printf("%lld\n", DP[1][n]); } return 0; }

파일 합치기 역시

연쇄 행렬의 최소 곱셈 알고리즘을 이용해야한다

(30 40) (50 50)

((30 4) (50 50))

과

(30 40) 50 50

((30 40) 50) 50

(((30 40) 50) 50)

은 다른 값을 도출해내기 때문이다

따라서 같은 알고리즘을 이용했는데 대신 뒤에 sum이라는 새로운 공식이 나온것 을 볼 수 있다

이것은 부분합을 이용한 것인데 

start부터 end까지의 전체합을 더해주는 것이다.

아직 공부한지 얼마 안되서 인지.. 연쇄 행렬의 최소 곱셈이 익숙해지지 않는다

비슷한 문제를 많이 풀어서 익숙해지도록 만들어야겠다.