/*
ID: ****
LANG: C
TASK: milk2
*/

/*#define __DEBUG__*/
#define MAX 1000000

#include 

int main()
{
	int N;
	int start, end;
	int **time;
	int count = 0;
	int modified = 0;
	int i,j;
	int milkTime = 0;
	int restTime = 0;
	int temp;

#ifndef __DEBUG__
	FILE *fin;
	FILE *fout;

	fin = fopen("milk2.in","r");
	fout = fopen("milk2.out","w");
	fscanf(fin, "%d", &N);
#else
	printf("input the number of farmers : ");
	scanf("%d", &N);
#endif

	time = (int**)malloc(sizeof(int*)*N);

	for(i=0 ; i < N ; i++)
	{
		time[i] = (int*)malloc(sizeof(int)*2);
#ifndef __DEBUG__
		fscanf(fin, "%d %d", &start, &end);
#else
		printf("input start time and end time.n[start time] [end time]n");
		scanf("%d %d", &start, &end);
#endif
		for (j=0 ; j < count ; j++)
		{
			if (start <= time[j][1] && end >= time[j][1])
			{
				time[j][1] = end;
				modified = 1;
			}
			if (end >= time[j][0] && start < = time[j][0])
			{
				time[j][0] = start;
				modified = 1;
			}
		}

		if (modified == 0)
		{
			time[j][0] = start;
			time[j][1] = end;
			count ++;
		}
		modified = 0;
	}

	for (i=0 ; i < count ; i++)
	{
		for (j=0 ; j < count ; j++)
		{
			if (time[i][0] <= time[j][1] && time[i][1] >= time[j][1])
			{
				time[j][1] = time[i][1];
			}
			if (time[i][1] >= time[j][0] && time[i][0] < = time[j][0])
			{
				time[j][0] = time[i][0];
			}
		}
	}

	for (i=0 ; i < count ; i++)
	{
		temp = time[i][1] - time[i][0];
		if (temp > milkTime)
		{
			milkTime = temp;
		}
	}

	for (i=0 ; i < count ; i++)
	{
		temp = MAX;
		for (j=0 ; j < count ; j++)
		{
			if (time[j][0] > time[i][1] && temp > time[j][0])
			{
				temp = time[j][0];
			}
		}

		if (temp == MAX)
		{
			continue;
		}

		temp = temp - time[i][1];

		if (temp > restTime)
		{
			restTime = temp;
		}
	}

#ifndef __DEBUG__
	fprintf(fout, "%d %dn", milkTime, restTime);
	fclose(fin);
	fclose(fout);
#else
	printf("the longest continuous time of milking : %dnthe longest idle time : %dn", milkTime, restTime);
#endif
	return 0;
}

매번 뻔한 코딩만하다보니 문제해결능력이 많이 떨어졌다는 것을 느낀다. 이번 문제는 여러 젖소가 우유를 짜는 시각이 주어지고, 최소한 한 젖소에서 우유를 짜는 가장 긴 시간과 전혀 우유를 짜지 않는 가장 긴 시간을 구하는 문제였다.

최소한 한 젖소에서 우유를 짜는 가장 긴 시간은 금새 구할 수 있었지만, 우유를 짜지 않는 가장 긴 시간을 구하는 것은 쉽게 나오지 않았다.

'Developing' 카테고리의 다른 글

USACO Training - Dual Plindromes  (0) 2007.12.15
파이썬 문자열 뒤집기  (0) 2007.11.17
이클립스에서 EUC-KR 문서 이용  (0) 2007.11.08

+ Recent posts