[H1733] 보석상 홍준

#include <stdio.h> #define MAX_BEA (30000000*32) #define MAX_SIZE 10000   typedef struct _GEM {     int price, beauti;     double efficience; }GEM;   typedef struct _BRANCHBOUND {     int level, price, beauti, bound; }BB;   BB heap[MAX_SIZE]; int heapSize = 0;   int TC, N, gemCnt, X, K, have; GEM gem[32];   int calcBound(int level, int price, int b) {     for (level; level < N && b+ gem[level].beauti <= X; level++) {         price += gem[level].price;         b += gem[level].beauti;     }     if (level < N && b < X && b + gem[level].beauti >= X) {         price += (X - b) / gem[level].efficience;         b = X;     }       if (b < X) return -1;       return price; }   void Swap(int i, int j) {     BB temp;     temp.beauti = heap[i].beauti;     temp.price = heap[i].price;     temp.bound = heap[i].bound;     temp.level = heap[i].level;       heap[i].beauti = heap[j].beauti;     heap[i].price = heap[j].price;     heap[i].bound = heap[j].bound;     heap[i].level = heap[j].level;       heap[j].beauti = temp.beauti;     heap[j].price = temp.price;     heap[j].bound = temp.bound;     heap[j].level = temp.level; }   void heapPush(BB branch) {     heap[heapSize].level = branch.level;     heap[heapSize].beauti = branch.beauti;     heap[heapSize].bound = branch.bound;     heap[heapSize].price = branch.price;       int current = heapSize;     while (current > 0 && heap[current].bound < heap[(current - 1) / 2].bound)     {         Swap(current, (current - 1) / 2);         current = (current - 1) / 2;     }       heapSize = heapSize + 1; }   void heapPop(BB* pop) {     if (heapSize <= 0)     {         return;     }       pop->beauti = heap[0].beauti;     pop->bound = heap[0].bound;     pop->level = heap[0].level;     pop->price = heap[0].price;       heapSize = heapSize - 1;       heap[0] = heap[heapSize];       int current = 0;     while (current * 2 + 1 < heapSize)     {         int child;         if (current * 2 + 2 == heapSize)         {             child = current * 2 + 1;         }         else         {             child = heap[current * 2 + 1].bound < heap[current * 2 + 2].bound ? current * 2 + 1 : current * 2 + 2;         }           if (heap[current].bound < heap[child].bound)         {             break;         }           Swap(child, current);         current = child;     } }   void gemSwap(int i, int j) {     GEM temp;     temp.beauti = gem[i].beauti;     temp.price = gem[i].price;     temp.efficience = gem[i].efficience;           gem[i].beauti = gem[j].beauti;     gem[i].price = gem[j].price;     gem[i].efficience = gem[j].efficience;       gem[j].beauti = temp.beauti;     gem[j].price = temp.price;     gem[j].efficience = temp.efficience; }   void init() {     heapSize = 0;     gemCnt = 0;     have = 0;     scanf("%d", &N);       for (int i = 0; i < N; i++)         scanf("%d", &gem[i].price);           for (int i = 0; i < N; i++) {         scanf("%d", &gem[i].beauti);         gem[i].efficience = gem[i].beauti / (double)gem[i].price;     }       scanf("%d%d", &X, &K);     for (int i = 0; i < K; i++) {         int temp;         scanf("%d", &temp);         have += gem[temp - 1].price;     }       for (int i = 0; i < N - 1; i++) {         double max = 0;         int maxIdx = 0;           for (int j = i; j < N; j++) {             if (gem[j].efficience > max) {                 max = gem[j].efficience;                 maxIdx = j;             }         }         gemSwap(i, maxIdx);     }   }   int main() {     scanf("%d", &TC);       for (int tc = 1; tc <= TC; tc++) {         init();                   BB current, add, nonAdd;         current.beauti = 0;         current.level = 0;         current.price = 0;         current.bound = calcBound(0, 0, 0);         heapPush(current);           int min = MAX_BEA;           if (current.bound == -1) {             heapSize = 0;             min = -1;         }           while (heapSize) {             heapPop(¤t);             if (current.bound == -1 || current.bound >= min) continue;             if (current.beauti >= X && current.price < min) {                 min = current.price;                 continue;             }               add.beauti = current.beauti + gem[current.level].beauti;             add.level = current.level + 1;             add.price = current.price + gem[current.level].price;             add.bound = calcBound(add.level, add.price, add.beauti);             if(add.bound != -1 && add.bound <min)                 heapPush(add);               nonAdd.beauti = current.beauti;             nonAdd.level = current.level + 1;             nonAdd.price = current.price;             nonAdd.bound = calcBound(nonAdd.level, nonAdd.price, nonAdd.beauti);             if (nonAdd.bound != -1 && nonAdd.bound <min)                 heapPush(nonAdd);         }           printf("#%d ", tc);         if (min == -1) printf("-1\n");         else {             min -= have;             if (min <= 0) min = 0;             printf("%d\n", min);         }     }       return 0; }

※ 문제 및 풀이에 대해 사외 온라인/오프라인에 게시/공유 하는 것은 금지되어 있습니다.      SW Expert 아카데미의 문제는 삼성전자 직원에게만 오픈 되어 있습니다.  [제한 사항] 시간 23개 테스트케이스를 합쳐서 C/C++의 경우 2초 / Java의 경우 5초 / Python의 경우 5초     메모리 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내   잉글랜드의 유명한 보석상 홍준은 사업 확장을 꾀하고 있다. 보석을 끔찍이도 아끼는 홍준은 눈물을 머금고 보석을 사고 팔아서 돈을 마련해야 한다. 시장에서 취급하는 보석은 1번부터 N번까지 총 N가지가 있으며 각각 미적 가치와 가격이 알려져 있다. 미적 가치는 해당 보석의 아름다운 정도를 수치화 한 것이고, 가격은 해당 보석을 팔았을 때 얻을 수 있는 돈이다. 홍준은 그 중에 K가지 보석을 가지고 있다. 시장에서 취급하는 모든 보석은 세상에 단 하나뿐이다. 홍준의 사업 확장을 위해서는 가지고 있는 보석들의 미적 가치의 총 합이 X만큼 필요하다. 그래야 사업 확장 허가가 떨어지기 때문이다. 홍준은 기존의 보석들을 시장에 팔 수도 있고 시장에서 보석을 살 수도 있다. 그러기 위해서는 초기 자본이 어느 정도 필요하다. 보석들의 정보와 필요한 미적 가치 X가 주어졌을 때, X 이상의 미적 가치를 마련하는 데에 필요한 최소 초기 자본을 구하여라.   [입력] 첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 1. 각 테스트 케이스의 첫 번째 줄에는 보석의 종류 N(1 ≤ N ≤ 32)이 주어진다. 2. 두 번째 줄에는 1번 보석부터 차례대로 각 보석의 가격이 주어지며 모두 30,000,000 이하의 자연수이다. 3. 세 번째 줄에는 1번 보석부터 차례대로 각 보석의 미적 가치가 주어지며 모두 30,000,000 이하의 자연수이다. 4. 네 번째 줄에는 필요한 미적 가치 X(1 ≤ X ≤ 1,000,000,000)가 주어진다. 5. 다섯 번째 줄에는 가지고 있는 보석의 수 K(0 ≤ K ≤ N)가 주어진다. 만약 K가 0이 아니라면, 여섯 번째 줄에는 가지고 있는 보석 번호가 K개 주어진다.   [출력] 각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 각 테스트 케이스마다 총 미적 가치가 X 이상이 되기 위해 필요한 최소한의 초기 자본을 출력한다. 아무리 돈이 많아도 마련할 수 없을 때에는 -1을 출력한다.   입력 예제   3 3 5 4 1 9 2 8 10 1 1 3 5 4 1 9 2 8 10 0 3 5 4 1 9 2 8 20 2 1 2 // 테스트 케이스 개수 // 첫 번째 테스트 케이스, N = 3           // 두 번째 테스트 케이스, N = 3         // 세 번째 테스트 케이스, N = 3           출력 예제   #1 0 #2 5 #3 -1 // 첫 번째 테스트 케이스 결과 // 두 번째 테스트 케이스 결과 // 세 번째 테스트 케이스 결과   [예제 설명] 첫 번째 예제의 경우, 초기에 0원이 있다고 하자. 1번 보석을 시장에 팔면 5원을 벌게 된다. 따라서 총 5원을 가지고 2번 보석과 3번 보석을 구매할 수 있다. 이 때 가지고 있는 총 보석의 가치가 10이 되므로, 사업 확장 신청이 가능하다. 따라서 필요한 최소 초기 자본은 0원이다.   두 번째 예제의 경우, 초기에 5원이 있다고 하자. 이 돈을 가지고 2번 보석과 3번 보석을 구매할 수 있다. 이 때 가지고 있는 총 보석의 가치가 10이 되므로, 사업 확장 신청이 가능하다. 따라서 필요한 최소 초기 자본은 5원이다.   세 번째 예제의 경우, 돈이 매우 많아서 모든 보석을 사도 미적 가치의 총 합이 19 이기 때문에 사업 확장 신청이 불가능하다.