PKU 1989. The Cow Lineup. [판정:TLE]

Solutions/Mr.K's Solution

Milkskin 2010. 1. 17. 03:24

일단, 제 문제해석에 댓글달아주신 milk님 감사합니다 (__)

기존의 알고리즘을 접어두고 이 방법으로 주워먹기하려 했으나

결과는 이렇네요 ㅋㅋ (가장 최근의 2건)

아무래도 소수열을 전부 살펴보는 것이다보니 N이 커지면서 시간이 많이 증가하는듯 합니다

시간 줄이는 방법을 좀 연구해봐야 할듯;

#include <iostream>

int N, K;
int *cows;

void clear( int ary[], int sz );
int seek( int ary[] );

int main()
{
	int i;

scanf("%d %d", &N, &K);

cows = new int[N];

for( i = 0; i < N; i++ )
	{
		scanf("%d", &cows[i]);
	}

printf("%d\n", seek(cows));

return 0;
}

void clear( int ary[], int sz )
{
	int i;

for( i = 0; i < sz; i++ ) ary[i] = 0;
}

int seek( int ary[] )
{
	if( K == 1 ) return N+1;

if( K > N ) return 1;

int i, j;
	int *check = new int[K+1];
	int bound;
	int sets;

if( N % K == 0 ) bound = N / K;
	else bound = N / K + 1;

for( i = 1; i <= bound; i++ )
	{
		sets = 0;
		clear(check, K+1);

for( j = 0; j < N; j++ )
		{
			/*
			if( check[cows[j]] == 0 )
			{
				check[cows[j]] = 1;
				check[0] += 1;
			}

if( check[0] == K )
			{
				sets += 1;

if( sets >= i )	break;
				else clear(check, K+1);
			}
			*/

if( check[cows[j]] < 1+sets )
			{
				check[cows[j]] += 1;
				check[0] += 1;
			}

if( check[0] == K*(1+sets) )
			{
				sets += 1;

if( sets >= i )	break;
			}
		}

if( sets < i ) return i;
	}

return bound+1;
}