[Algorithm] Microwaving Lunch Boxes (Algospot – LUNCHBOX)

출처

• 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", &microTime[i]);
		}
		for (int i = 0; i < inputSize; i++) {
			scanf("%d", &eatingTIme[i]);
		}
		sort(0, inputSize-1);
		//printList();
		printf("%d\n", findAnswer());
	}
	return 0;
}