📝 문제 정보#
🧐 관찰 및 접근#
- 파일 $C_i, C_{i+1}, \cdots, C_{j}$를 합치고 싶다고 하자.
- 이때, 해당 값은 $\text{DP}[i][j] = min_{i \leq k < j}(\text{DP}[i][k] + \text{DP}[k+1][j])$이 성립한다.
- 이는 $O(N^3)$이므로 충분히 돈다.
- 이런 문제는 top-down 재귀 DP로 구현하면 조금 더 편하게 짤 수 있다.
- TMI) 크누스 최적화를 이용해 더 빠르게도 풀 수 있다!
💻 풀이#
- 코드 (C++):
ll calc(int L, int R){
if(L == R) return 0;
ll &ret = DP[L][R];
if(ret != -1) return ret;
ret = LLONG_MAX;
rep(k, L, R) ret = min(ret, calc(L, k) + calc(k+1, R) + (pfsum[R] - pfsum[L-1]));
return ret;
}
void solve(){
cin >> N;
rep(i, 1, N+1) cin >> C[i];
rep(i, 1, N+1) pfsum[i] = pfsum[i-1] + C[i];
rep(i, 1, N+1) rep(j, 1, N+1) DP[i][j] = -1;
cout << calc(1, N) << '\n';
}