본문 바로가기

난 이 분야 전문가야!/Algorithm

[백준][C] 2994 내한 공연 - 풀이 공유

https://www.acmicpc.net/problem/2994

 

2994번: 내한 공연

문제 "The Drinking Musicians"는 2034년 그래미 어워즈에서 총 6관왕에 오른 유명한 N인조 밴드이다. 이 밴드의 음악은 엄청난 힘을 가지고 있어서, 사람의 생각을 조절할 수 있다. 대표적인 예로 결혼식에서 이 밴드의 "그 남자가 저기 있어"를 축가로 부르면, 모든 신부가 그 남자를 찾아 결혼식장을 나선다고 한다. 이 밴드의 공연을 보는 것은 쉽지 않다. 밴드는 정시에 도착하지 않으며, 공연장의 위치도 잘 모른다. 또, 공연장에 도착했

www.acmicpc.net

이번 문제는 0/1 냅색 문제의 응용버전이라고 생각합니다.

뒤에 백스테이지에서의 휴식시간은 냅색에서 가방의 용량(weight), 맴버들이 휴식을 취한 시간을 값(value)이라 생각하고 최대한 두명이 휴식을 취할수 있다하니 백스테이지의 휴식공간이 2개 있다고 생각합시다.

(냅색으로 치면 가방이 두개라고 생각하면 됩니다.)

문제에서 항상 답이 존재한다고 하였으니 휴식 공간 하나를 최대 value로 채우면 나머지 휴식 공간은 휴식을 취하지 않은 맴버를 차례대로 다 집어넣으면 됩니다.

 

DP 알고리즘을 사용하였으며 공유 차원에서 올린 코드이니 참고하시고 더 좋은 코드를 작성해 보시기 바랍니다.

(코드가 너무 더러워서 풀이 설명할 엄두가 안난다... 나중에 다른 방식으로 풀거나 해야겠다.)

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
 
int data[501];   // 맴버들의 휴식 시간을 저장 
int** p;         // 다이나믹 프로그래밍에 사용될 2차원 배열
int*** used;     // 휴식을 취한 맴버의 index를 저장
int time = 0;
 
void copyAry(int i1, int c1, int i2, int c2) {        // 리스트 복사
    for (int j = 0; j <= used[i2][c2][0]; j++) {
        used[i1][c1][j] = used[i2][c2][j];
    }
}
 
int main() {
    int T, N;
    int i, c, cur, past;       
    int result[501];
 
    scanf("%d %d"&T, &N);
 
    used = (int***)malloc(sizeof(int*** 2);
    for (i = 0; i < 2; i++) {
        used[i] = (int**)malloc(sizeof(int** (T + 1));
        for (c = 0; c <= T; c++) {
            used[i][c] = (int*)malloc(sizeof(int** N);
        }
    }
 
    p = (int**)malloc(sizeof(int** (N + 1));
    for (int i = 0; i <= N; i++) {
        p[i] = (int*)malloc(sizeof(int* (T + 1));
    }
 
    for (i = 1; i <= N; i++)
        scanf("%d"&data[i]);
 
    for (i = 0; i <= N; i++)        // DP
    {
        if (i % 2) {     // 메모리 공간을 줄이기 위해,  used 배열의 전 단계와 현제 단계를 돌아가면서 사용
            cur = 1;      // cur 현재 단계   past 전 단계
            past = 0;
        }
        else {
            cur = 0;
            past = 1;
        }
 
        for (c = 0; c <= T; c++)                
        {
            if (i == 0 || c == 0)
            {
                p[i][c] = 0;
                used[cur][c][0= 0;
            }
            else if (data[i] > c)
            {
                p[i][c] = p[i - 1][c];
                copyAry(cur, c, past, c);
            }
            else
            {
                if (p[i - 1][c] >= data[i] + p[i - 1][c - data[i]])
                {
                    p[i][c] = p[i - 1][c];
                    copyAry(cur, c, past, c);
                }
                else
                {
                    p[i][c] = data[i] + p[i - 1][c - data[i]];
                    copyAry(cur, c, past, c - data[i]);
                    used[cur][c][0+= 1;
                    used[cur][c][used[cur][c][0]] = i;
                }
            }
        }
    }
                                                   // p[N][T] = 휴식시간을 최대한 남김없이 사용했을때의 총 휴식시간
 
    for (i = 1; i <= used[cur][T][0]; i++) {           // used[cur][T][0] = p[N][T]휴식을 취한 맴버
        result[used[cur][T][i]] = time;
        time += data[used[cur][T][i]];
        data[used[cur][T][i]] = -1;
    }
 
    time = 0;
 
    for (i = 1; i <= N; i++) {                       // 다른 휴식 공간,  p[N][T]에 없는 맴버
        if (data[i] != -1) {
            result[i] = time;
            time += data[i];
        }
    }
 
    for (i = 1; i <= N; i++
        printf("%d ", result[i]);
 
    return 0;
}
cs

 

 

728x90