11066. 파일 합치기


문제

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

예를 들어, C1, C2, C3, C4가 연속적인 네 개의 장을 수록하고 있는 파일이고, 파일 크기가 각각 40, 30, 30, 50 이라고 하자. 이 파일들을 합치는 과정에서, 먼저 C2와 C3를 합쳐서 임시파일 X1을 만든다. 이 때 비용 60이 필요하다. 그 다음으로 C1과 X1을 합쳐 임시파일 X2를 만들면 비용 100이 필요하다. 최종적으로 X2와 C4를 합쳐 최종파일을 만들면 비용 150이 필요하다. 따라서, 최종의 한 파일을 만드는데 필요한 비용의 합은 60+100+150=310 이다. 다른 방법으로 파일을 합치면 비용을 줄일 수 있다. 먼저 C1과 C2를 합쳐 임시파일 Y1을 만들고, C3와 C4를 합쳐 임시파일 Y2를 만들고, 최종적으로 Y1과 Y2를 합쳐 최종파일을 만들 수 있다. 이 때 필요한 총 비용은 70+80+150=300 이다.

소설의 각 장들이 수록되어 있는 파일의 크기가 주어졌을 때, 이 파일들을 하나의 파일로 합칠 때 필요한 최소비용을 계산하는 프로그램을 작성하시오.

입력

프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, 첫 행에는 소설을 구성하는 장의 수를 나타내는 양의 정수 K (3 ≤ K ≤ 500)가 주어진다. 두 번째 행에는 1장부터 K장까지 수록한 파일의 크기를 나타내는 양의 정수 K개가 주어진다. 파일의 크기는 10,000을 초과하지 않는다.

출력

프로그램은 표준 출력에 출력한다. 각 테스트 데이터마다 정확히 한 행에 출력하는데, 모든 장을 합치는데 필요한 최소비용을 출력한다.

예제 입력 

2
4
40 30 30 50
15
1 21 3 4 5 35 5 4 3 5 98 21 14 17 32

예제 출력 

300
864


1. 접근


예시 테스트 케이스 중 첫 번째 경우에 대해 생각해보자.


{40, 30, 30, 50} 을 우선 두 그룹으로 나눠야 한다. 나눠지는 경우의 수는 여러가지일 것이다.

{40} / {30, 30, 50} 으로 나눈 경우에, 뒷 그룹 또한 더 나눠지는 방법이 존재한다.


따라서 단순히 테스트 케이스를 계속 두 그룹으로 나누는, 즉 이진 트리를 만드는 모든 방법에 대해 최소 비용을 계산해야 한다.

하지만 같은 데이터를 중복해서 연산하는 과정이 겹치기 때문에, 메모이제이션을 통한 다이나믹 프로그래밍 기법을 통해 접근해야 한다.


2-1) 풀이 1.


novel[i] = 소설의 i번째 장의 크기라 하고, 

다이나믹 프로그래밍 기법을 통해, 점화식을 세우기 위한 배열 dp[i][j]를 정의해보자.


dp[i][j]  = i번째 장부터 j번째 장까지 합치는데 드는 최소한의 비용.


따라서 dp[i][i] = novel[i], dp[i][i+1] = novel[i]+novel[i+1] 임을 쉽게 알 수 있다.

또한 dp[i][j] 를 두 그룹으로 나누는 기준이 되는 k에 대해(i<=k<j) 다음 점화식을 생각할 수 있다.


dp[i][j] = min(i <= k < j){dp[i][k] + dp[k+1][j]} + psum[i][j] (psum[i][j] 는 novel[i][j] 의 i부터 j까지의 부분합)


결국 삼중 포문을 돌면서 dp[][] 를 갱신해가면서, 최종적으로 dp[1][N] 을 출력하면 되는 문제였다. O(N^3)


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
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <algorithm>
using namespace std;
 
int dp[501][501];
int cost[501];
int sum[501];
int t, k, i;
 
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &k);
        for (i = 1; i <= k; ++i) {
            scanf("%d", &cost[i]);
            sum[i] = sum[i - 1] + cost[i];
        }
 
        for (int d = 1; d < k; ++d) {
            for (int tx = 1; tx + d <= k; ++tx) {
                int ty = tx + d;
                dp[tx][ty] = INT_MAX;
 
                for (int mid = tx; mid < ty; ++mid)
                    dp[tx][ty] =
                        min(dp[tx][ty], dp[tx][mid] + dp[mid + 1][ty] + sum[ty] - sum[tx - 1]);
            }
        }
 
        printf("%d\n", dp[1][k]);
    }
    return 0;
}
cs


2-2) 풀이 2.

1의 풀이가 밑에서 부터 채워나가는 방법이였다면, 가장 범위가 넓은 경우부터 따져나가는 방법도 있을 것이다.

예를 들어, 6개의 파일에 대해 dp[1][6]을 채우는 방법은, 어느 기점을 기준으로 왼쪽 최소비용, 오른쪽 최소비용의 합이다.

그 중 왼쪽은 다시 어느 기점을 기준으로 왼쪽 최소비용, 오른쪽 최소비용의 합으로 이루어져 있을 것이다.

이렇게 계속 재귀적으로 나누어가다 보면 더이상 쪼개지지 않는 경우에 도달하고, (파일이 한개라면 비용은 0이다)

이 비용을 리턴받아 왼쪽, 오른쪽 최소비용을 채워나간다.

코드로 옮기자면 다음과 같다.

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
 
int dp[501][501];
int cost[501];
int sum[501];
int t, k, i;
 
int dpf(int tx, int ty) {
    if (dp[tx][ty] != 0x3f3f3f3f)
        return dp[tx][ty];
 
    if (tx == ty)
        return dp[tx][ty] = 0;
 
    if (tx + 1 == ty)
        return dp[tx][ty] = cost[tx] + cost[ty];
 
    for (int mid = tx; mid < ty; ++mid) {
        int left = dpf(tx, mid);
        int right = dpf(mid + 1, ty);
        dp[tx][ty] = min(dp[tx][ty], left + right);
    }
 
    return dp[tx][ty] += sum[ty] - sum[tx - 1];
}
 
int main() {
    scanf("%d", &t);
    while (t--) {
        memset(dp, 0x3f, sizeof(dp));
        scanf("%d", &k);
        for (i = 1; i <= k; ++i) {
            scanf("%d", &cost[i]);
            sum[i] = sum[i - 1] + cost[i];
        }
        printf("%d\n", dpf(1, k));
    }
    return 0;
}
cs

두 파일에 대해 합치는 비용은 두 파일 크기의 합과 같다.

그럼 세 파일에 대해 합치는 비용의 경우 중 한 가지, {{1+2}+{3}} 은 왼쪽을 합치는 비용(3) 과 오른쪽을 합치는 비용(0)에

전체 구간의 파일 크기의 합과 같다. 

이 작은 케이스를 가장 큰 케이스에 투영 시키는 것이다.

2-2) 풀이 3.


풀이 1 대로면 대략 125,000,000 번의 연산으로 140ms 정도로 AC를 받는다.

풀이 2 대로면 대략 125,000,000 번의 연산으로 580ms 정도로 AC를 받는다. (함수호출등의 이유로 더 오래 걸린 것이다)


하지만 맞은 사람들의 코드들을 보면 대부분 20ms 내외로 AC를 받았는데, 감명깊어 여기에 풀이를 옮긴다.


기본 아이디어는 같으나 결과적으론 최적화의 문제인데,

다이나믹 프로그래밍 문제 중에 다음과 같은 특별한 점화식에 대해서 최적화가 가능하다고 한다.

이를 Kruth's optimization 이라 부른다.


1) 사각부등식

C[a][c]+C[b][d]<=C[a][d]+C[b][c] (a<=b<=c<=d) 


2) 단조증가

C[b][c]<=C[a][d] (a<=b<=c<=d)


위 두 조건을 만족하는 C[][]에 대해,

점화식이 dp[i][j] = min(i < k < j){dp[i][k] + dp[k][j]} + C[i][j] 꼴이라 하자. 


이 때, num[i][j]란 dp[i][j]가 최소가 되게 하는 k(i < k < j)값을 저장하는 배열이라 정의하면, 다음이 성립한다.

num[i][j-1]  <= num[i][j] <= num[i+1][j]


풀이 1에선 i부터 j까지의 모든 k에 대해 최소값을 구하느라 O(N^3)이 걸렸지만,

실제로는 정답인 k가 저 좁은 범위안에 있기 때문에 모든 k를 살펴볼 필요가 없으므로 최적화가 O(N^2)로 가능하다는 이론이다.

증명은 다음페이지를 참조하자.

http://www.egr.unlv.edu/~bein/pubs/knuthyaotalg.pdf



실제로 최적화가 적용가능한지 살펴보기 위해, 먼저 우리의 psum[][] 배열이 C[][] 꼴 인지 생각해보자.

1) 사각부등식에 대해, 앞의 항과 뒤의 항 모두 b~c의 novel[][]를 중복해서 더하므로, 등호를 만족한다.

2) 단조증가에 대해, psum[b][c]<=psum[a][d] 임은 자명하다.


다음으로 점화식에 대해 생각해보면, 우리의 점화식은 다음과 같았다.


i<=k<j인 k에 대해,

dp[i][j] = min(i <= k < j){dp[i][k] + dp[k+1][j]} + psum[i][j] -> i부터 j까지의 최소합비용


이제 Kruth's optimization을 적용하기 위해, 점화식을 수정해주자.


i<k<j인 k에 대해,

dp2[i][j] = min(i < k < j){dp2[i][k] + dp2[k][j]} + psum[i][j] -> i + 1부터 j까지의 최소합비용


점화식이 조금 수정되었지만, dp[i][j] = dp2[i-1][j] 이기 때문에 여전히 같은 기능을 수행한다.

정답은 dp2[0][N]을 출력하면 된다.


d=2 부터, i=0 부터 시작하는 것을 주의하라.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main() {
    for (scanf("%d", &T); T--;) {
        scanf("%d", &N);
        for (int i = 1; i <= N; i++)
            scanf("%d", &novel[i]), psum[i] = psum[i - 1] + novel[i];
        for (int i = 1; i <= N; i++)
            num[i - 1][i] = i;
        for (int d = 2; d <= N; d++) {
            for (int i = 0; i + d <= N; i++) {
                int j = i + d;
                dp2[i][j] = 2e9;
                for (int k = num[i][j - 1]; k <= num[i + 1][j]; k++) {
                    int v = dp2[i][k] + dp2[k][j] + psum[j] - psum[i];
                    if (dp2[i][j] > v)
                        dp2[i][j] = v, num[i][j] = k;
                }
            }
        }
        printf("%d\n", dp2[0][N]);
    }
    return 0;
}
cs


3. 후기


알고나면 쉬운문제다. 하지만 여러 복합적인 기능들이 섞여있는 문제이기도 하다.

dp들을 갱신해가는 과정은 연쇄행렬 최소곱 알고리즘의 과정과 닮아있다.

'알고리즘 > Dynamic Programming 동적계획법' 카테고리의 다른 글

백준) 3032 승리(IVANA)  (0) 2017.08.23
백준) 11062 카드게임(Card Game)  (1) 2017.08.23
백준) 9657 돌 게임 3  (0) 2017.08.18
백준) 9656 돌 게임 2  (0) 2017.08.17
백준) 9655 돌 게임  (0) 2017.08.17

1194 달이 차오른다, 가자.

문제

지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때 부터, 준비했던 여행길이다. 하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다.

민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되 버렸다. 결국 민식이는 모두 잠든 새벽 네시 반 홀로 일어나, 창 밖에 떠있는 달을 보았다.

하루밖에 남지 않았다. 달은 내일이면 다 차오른다. 이번이 마지막기회다. 이걸 놓치면 영영 못간다.

영식이는 민식이가 오늘도 여태것처럼 그냥 잠 들어버려서 못 갈지도 모른다고 생각했다. 하지만 그러기엔 민식이의 눈에는 저기 뜬 달이 너무나 떨렸다.

민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다. 미로는 다음과 같이 구성되있다.

  • 빈 곳 : 언제나 이동할 수 있다. ('.‘로 표시됨)
  • 벽 : 절대 이동할 수 없다. (‘#’)
  • 열쇠 : 언제나 이동할 수 있다. 이 곳에 처음 들어가게 되면 열쇠를 집는다. (소문자 a - f)
  • 문 : 대응하는 열쇠가 있을 때만 이동할 수 있다. (대문자 a - f)
  • 민식이의 현재 위치 : 빈 곳이고, 민식이가 현재 서 있는 곳이다. (숫자 0)
  • 출구 : 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. (숫자 1)

달이 차오르는 기회를 놓치지 않기 위해서, 되도록 미로를 탈출하려고 한다. 한 번의 움직임은 현재 위치에서 수평이나 수직으로 한 칸 이동하는 것이다.

민식이가 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (N,M <= 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 영식이가 열쇠를 숨겨놓는 다면 문에 대응하는 열쇠가 없을 수도 있다. 0은 한 개, 1은 적어도 한 개 있다. 그리고, 열쇠는 여러 번 사용할 수 있다.

출력

첫째 줄에 민식이가 미로를 탈출하는데 드는 이동 횟수의 최솟값을 출력한다. 만약 민식이가 미로를 탈출 할 수 없으면, -1을 출력한다.

예제 입력 

1 7
f0.F..1

예제 출력 

7



1. 접근


행렬을 순회하면서 최소 이동 횟수를 찾아야 하기 때문에 BFS를 채용.


2. 세부사항


열쇠를 습득했는지 여부에 따라 이동방식이 바뀌기 때문에 매번 방문시 열쇠 보유 상태를 갱신하고 기억해야한다.

따라서 삼차원 행렬을 BFS로 순회하면서 탐색한다. X, Y 축이 미로이고, Z축이 열쇠 보유 상태인 셈.

시작점이 주어지고 지도에서 1을 찾으면 종료되므로,

최악의 경우 모든 지점을 방문하는 N*M*(가능한 열쇠보유 상태의 경우)에 비례.


3. 코드


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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
 
char map[50][51];
int visit[50][50][1 << 7]; //6자리 2진수를 만들기 위해 7번 시프트
int d[4][2] = { {-1, 0},{1, 0},{0, -1},{0, 1} };
int n, m, stx, sty;
 
int bfs() {
    visit[stx][sty][0] = 1;
    queue<pair<pair<int, int>, int>> q;
    q.push({ {stx, sty}, 0 });
 
    while (!q.empty()) {
        int qs = q.size();
        while (qs--) {
            int x = q.front().first.first;
            int y = q.front().first.second;
            int k = q.front().second;
            q.pop();
 
            if (map[x][y] == '1')
                return visit[x][y][k] - 1;
 
            for (int i = 0; i < 4; ++i) {
                int xx = x + d[i][0];
                int yy = y + d[i][1];
 
                if (xx < 0 || yy < 0 || xx >= n || yy >= m || map[xx][yy] == '#' || visit[xx][yy][k] != 0)
                    continue;
                if ('a' <= map[xx][yy] && map[xx][yy] <= 'f') {
                    int kk = k | (1 << (map[xx][yy] - 'a')); // OR연산으로 열쇠보유상태를 갱신
                    if (visit[xx][yy][kk] == 0) {
                        visit[xx][yy][k] = visit[x][y][k] + 1;
                        visit[xx][yy][kk] = visit[x][y][k] + 1;
                        q.push({ {xx, yy}, kk });
                    }
                }
                else if ('A' <= map[xx][yy] && map[xx][yy] <= 'F') {
                    int kk = k & (1 << (map[xx][yy] - 'A')); // AND연산으로 해당 열쇠를 보유 중인지 확인
                    if (kk != 0) {
                        visit[xx][yy][k] = visit[x][y][k] + 1;
                        q.push({ {xx, yy}, k });
                    }
                }
                else if (visit[xx][yy][k] == 0) {
                    visit[xx][yy][k] = visit[x][y][k] + 1;
                    q.push({ {xx, yy}, k });
                }
            }
        }
    }
    return -1;
}
 
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%s", map[i]);
        for (int j = 0; j < m; ++j) {
            if (map[i][j] == '0') {
                stx = i;
                sty = j;
            }
        }
    }
    printf("%d", bfs());
 
    return 0;
}
cs


4. 후기


열쇠 보유 상태를 어떤 형식으로 저장해야 하는지 한참 헤맸다.

비트마스킹 기법을 새롭게 알게 되었으니 기억하도록 하자.

처음 제출 했을 당시엔 열쇠 상태 갱신에만 신경쓰다보니 메모리 초과가 떴다.

열쇠 레벨로 올라가고 (Z축) 큐에 남겨진 기존 레벨들의 탐색을 처리해주지 않아서 였다.

'알고리즘 > 브루트 포스' 카테고리의 다른 글

백준) 2178 미로 탐색  (3) 2017.10.09
백준) 7569 토마토  (3) 2017.09.28
백준) 7576 토마토  (0) 2017.09.28
백준) 9466 텀 프로젝트  (0) 2017.09.03
백준) 2667 단지번호붙이기  (0) 2017.07.07

2667. 단지번호붙이기


문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

예제 입력 

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

예제 출력 

3
7
8
9


1. 접근


DFS/BFS 문제.

모든 행렬을 순회해야 하므로 N^2 안에 수행.



2. 세부사항


모든 행렬을 순회하면서 1이면 DFS/BFS를 수행한다.

수행 시작시에 카운트용 변수를 선언해서 순회 중에 만난 1의 수를 저장하고, 수행이 끝나면 최종적인 카운트 값을 저장한다.

최후에 저장된 카운트들을 오름차순 정렬하고, 개수와 각 카운트들을 출력한다.



3. 코드


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
44
45
46
47
48
49
50
51
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
 
int n;
int map[25][25];
int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
int que[50];
char buf[26];
 
int dfs(int x, int y) {
    int cnt = 1;
    map[x][y] = 2;
 
    for (int i = 0; i < 4;++i) {
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
 
        if (xx < 0 || xx >= n || yy < 0 || yy >= n)
            continue;
        if (map[xx][yy] != 1)
            continue;
 
        cnt += dfs(xx, yy);
    }
    return cnt;
}
 
int main() {
    scanf("%d", &n);
 
    for (int i = 0; i < n; ++i) {
        scanf("%s", buf);
        for (int j = 0; j < n; ++j)
            map[i][j] = buf[j] - '0';
    }
 
    int cnt = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            if (map[i][j] == 1)
                que[cnt++] = dfs(i, j);
 
    printf("%d\n", cnt);
    sort(que, que + cnt);
    for (int i = 0; i < cnt; ++i)
        printf("%d\n", que[i]);
 
    return 0;
}
cs


'알고리즘 > 브루트 포스' 카테고리의 다른 글

백준) 2178 미로 탐색  (3) 2017.10.09
백준) 7569 토마토  (3) 2017.09.28
백준) 7576 토마토  (0) 2017.09.28
백준) 9466 텀 프로젝트  (0) 2017.09.03
백준) 1194 달이 차오른다, 가자.  (0) 2017.07.07

+ Recent posts

티스토리툴바