Suhwanc

문제 링크 : https://www.acmicpc.net/problem/11066

 

11066번: 파일 합치기

문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을

www.acmicpc.net

 

문제 요약

여러 파일들이 주어졌을 때 파일들을 두 개씩 합쳐서 여러 장들이 연속이 되도록 파일을 합쳐나가

최종적으로 하나의 파일로 되도록한다.

두 개의 파일으 합칠 때 필요한 비용은 두 파일 크기의 합이며 출력값으로 최종 파일을 완성하는데 필요한 비용의 총 합을 출력한다.

풀이

다이나믹 프로그래밍 문제입니다!

이 문제가 dp로 풀 수 있는 이유는 바로 위에 빨간 색으로 강조한 "여러 장들이 연속이 되도록" 이라는 조건 때문이다.

예를 들어 연속적인 파일 C1, C2, C3, C4 가 있다면 이 파일들을 두 그룹으로 나눌 수 있게된다.

  • (C1)(C2,C3,C4)
  • (C1,C2)(C3,C4)
  • (C1,C2,C3)(C4)

그럼 이 그룹들은 각각의 부분 문제들이 되기 때문에 dp를 이용 가능하다.

이 문제에서 d[i][j]는 파일 i ~ 파일 j 를 합치는데 드는 비용의 최소값이고,

두 그룹을 나누기 위한 중간 값 k를 만들어줘야한다.

위의 예시에서 k는 순서대로 1,2,3 이 된다. (k의 범위는 0 ~ j-1)

따라서

  • d[i][j] = d[i][k] * d[k+1][j] + (i~j를 합치는데 드는 비용) 

이렇게 만들어준 부분 문제들을 다시 재귀호출한다.

 

소스 코드

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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
 
int d[501][501]; // d[i][j] : i~j 합의 최소비용
int a[501];
 
int go(int i, int j) {
    //기저 사례
    if (i == j) return 0;
    if (d[i][j] != -1return d[i][j]; //이미 계산했다면
    int sum = 0;
    int &ans = d[i][j];
    for (int k = i; k <= j; k++) { //합치는데 드는 비용
        sum += a[k];
    }
    for (int k = i; k <= j - 1; k++) { //순서대로 분할
        int temp = go(i, k) + go(k + 1, j) + sum;
        if (ans == -1 || ans > temp) {
            ans = temp;
        }
    }
    return ans;
}
int main()
{
    int t; scanf("%d"&t);
    while (t--) {
        memset(d, -1sizeof(d));
        int k; scanf("%d"&k);
        for (int i = 1; i <= k; i++) {
            scanf("%d"&a[i]);
        }
        printf("%d\n", go(1, k));
    }
    return 0;
}
cs

 

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~

'백준 문제풀이' 카테고리의 다른 글

백준 5557번 1학년  (0) 2020.02.12
백준 13975번 파일 합치기 3  (0) 2020.02.12
백준 11066번 파일 합치기  (0) 2020.02.12
백준 2252번 줄 세우기  (0) 2020.02.12
백준 14503번 로봇 청소기  (0) 2020.01.27
백준 14499번 주사위 굴리기  (0) 2020.01.27