출처
- https://algospot.com/judge/problem/read/LUNCHBOX
- 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 (구종만)
난이도
- (하) – 중 – 상 – 최상 – 풀지못함
문제
- N개의 도시락을 데우는 시간과 먹는 시간이 주어진다. 도시락을 데울 수 있는 전자레인지가 1개 밖에 없다고 가정을 했을 때 모든 도시락을 다 데워서 먹는데 걸리는 최소한의 시간을 찾는 문제이다. 도시락은 무조건 한 번에 다 데워야 한다는 가정이 있다. 다시 말해서 중간에 멈췄다가 다시 데우면 처음부터 다시 데워야 한다는 의미이다.
후기
- 알고리즘 책에서 제공하는 문제이다. 항상 CH가 나누어져 있어서 당연히 탐욕법을 이용해서 문제를 풀어야 한다는 건 알고 있었다. 그래서 그런지 생각보다 문제가 너무 쉽게 풀렸다.
- 어떠한 순서로 도시락을 데워도 도시락을 데우는 시간은 절대로 변하지 않는다. 다시 말해서 도시락을 데우는 순서가 중요한 게 아니라, 먹는 속도가 중요하다는 의미이다. 그래서 도시락을 늦게 먹는 시간순으로 정렬을 하고 먹는 데 오랜 시간이 걸리는 도시락부터 순서대로 도시락을 데워서 먹으면 된다.
- 나의 경우 작은 수부터 나열하여서 역순으로 사용했다. 하지만, 책에서는 양수를 모두 음수로 만들어서 Sort 함수를 사용하면 큰 숫자 (큰 수가 제일 작은 수가 됨)부터 정렬된다. 계산할 때 숫자에 단순히 -1을 곱해서 사용하면 된다.
코드
- 탐욕법을 사용한 코드
- Github 주소: https://github.com/mkblog-cokr/algorithmCode
- 실행 시간: 40ms (제일 빠른 코드 대비 대략 5배 (8ms) 느림)
//MK: 탐욕방법을 사용한 문제 해결 코드 #include <stdio.h> //MK: Visual Studio를 사용시 scanf 에러 제거함 #pragma warning(disable: 4996) #define MAXSIZE 10000 #define MAX(a,b) (a)>(b)?(a):(b) int microTime[MAXSIZE]; int eatingTIme[MAXSIZE]; int inputSize; //MK: Quick Sort 코드 void sort(int lhs, int rhs) { if (lhs < rhs) { int i = lhs; int j = rhs; int p = lhs; while (i < j) { while (eatingTIme[i] <= eatingTIme[p] && i <= rhs) { i++; } while (eatingTIme[j] > eatingTIme[p]) { j--; } if (i < j) { int tmp = microTime[i]; microTime[i] = microTime[j]; microTime[j] = tmp; tmp = eatingTIme[i]; eatingTIme[i] = eatingTIme[j]; eatingTIme[j] = tmp; } } int tmp = microTime[j]; microTime[j] = microTime[p]; microTime[p] = tmp; tmp = eatingTIme[j]; eatingTIme[j] = eatingTIme[p]; eatingTIme[p] = tmp; sort(lhs, j - 1); sort(j + 1, rhs); } } //MK: Sort 여부를 확인 하기 위한 Print 코드 void printList() { for (int i = 0; i < inputSize; i++) { printf("(%d %d) - ", microTime[i], eatingTIme[i]); } printf("\n"); } //MK: 탐욕법을 사용하여 문제를 해결하는 코드 int findAnswer() { int ret = 0; int sumTime = 0; for (int i = inputSize-1; i >= 0; i--) { sumTime += microTime[i]; ret = MAX(ret, sumTime + eatingTIme[i]); } return ret; } int main() { //freopen("input.txt", "r", stdin); int testCase = 0; scanf("%d", &testCase); for (int m = 1; m <= testCase; m++) { scanf("%d", &inputSize); for (int i = 0; i < inputSize; i++) { scanf("%d", µTime[i]); } for (int i = 0; i < inputSize; i++) { scanf("%d", &eatingTIme[i]); } sort(0, inputSize-1); //printList(); printf("%d\n", findAnswer()); } return 0; }