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

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

2994번: 내한 공연

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

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

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

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

 

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

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

#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;
}