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

일단, 제 문제해석에 댓글달아주신 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; }