문제 URL : https://www.acmicpc.net/problem/11066
11066번: 파일 합치기
소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본
www.acmicpc.net
문제 접근법 :
개인적으로 골드3문제가 맞나 싶을정도로 어려웠습니다. 이틀정도 고민하다 답을 봤는데도
답도 이해가안됨 그냥 분할정복으로 몇개의 답을 참고해서 분할문제로 생각하니
답이 보이네여
결국엔 최소비용을 구하는거지만 dp를 이용하여 가장최소가 되는것을 찾는데
(1,2,3,4) 인경우
()(1,2,3,4)
(1),(2,3,4)
(1,2),(3,4)
(1,2,3),(4)
(1,2,3,4),()
이런식으로 분할하고 또분할하면서 더했을때 최종적인 답을 내는문제입니다. 해결하니까 마음은 뿌듯하네요 ㅎㅎ
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
//by 콩순이냉장고
#include <bits/stdc++.h>
using namespace std;
#define v vector
#define vi v<int>
#define vvi v<vi>
vvi dp;
vi sv,sum;
int n;
void input() {
cin >> n;
sv = sum = vi(n + 1);
dp = vvi(n+1, vi(n+1, 1e8));
for (int i = 1; i <= n; i++) {
cin >> sv[i];
sum[i] += sum[i - 1] + sv[i];
}
}
int dfs(int left,int right) {
if (left > right)return 1e8;
int& res = dp[left][right];
if (left == right)return res = 0; //파일이 1개인경우
if (left + 1 == right)return res = sv[left] + sv[right];
if (res != 1e8) return res;
for (int i = left; i <= right; i++) {
res = min(res, dfs(left, i) + dfs(i + 1, right));
}
return res += sum[right] - sum[left - 1];
}
void solve() {
cout << dfs(1, n) << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int test;
cin >> test;
while (test--) {
input();
solve();
}
}
|
cs |
궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.
공감도 달아주실꺼죠??
'백준' 카테고리의 다른 글
| 백준 10835 카드게임 (0) | 2021.10.05 |
|---|---|
| 백준 16401 과자 나눠주기 (0) | 2021.10.05 |
| 백준 6324 URLs (0) | 2021.09.01 |
| 백준 1938 통나무 옮기기 (0) | 2021.08.31 |
| 백준 2842 집배원 한상덕 (0) | 2021.08.31 |
