PKU 1145, UVa 112. Tree Summing. [판정:AC & TLE]

#include <stdio.h> #include <math.h> #define SIZE 2000 int isInt( double x ) { if( floor(x) == ceil(x) ) return 1; else return 0; } int isInHere( int x, int here[] ) { int i; for( i = 0; here[i] != -1; i++ ) { if( here[i] == x ) return 1; } return 0; } void pullOut( int pullThis, double list[], int *endKey, int keyList[], int etcList[] ) { int i; int del = 0; for( i = pullThis; i < *endKey; i++ ) { list[ i-2 ] = list[ i+1 ]; } *endKey -= 3; for( i = 0; keyList[i] != -1; i++ ) { if( keyList[i]!=-2 && del==0 ) { keyList[i] = -2; del = 1; } else if( keyList[i]!=-2 && del==1 ) { keyList[i] -= 3; } } for( i = 0; etcList[i] != -1; i++ ) { etcList[i] -= 3; } } void main() { int searchKey; int compare; int type = 0; // 1 : digit, 0 : etc int i = 0; int j = 0; int length; // size of inputs int judge; int count = 0; // number of parenthesis char getter; double inputs[ SIZE ]; int leaves[ SIZE/5 ]; int branches[ SIZE/5 ]; while( scanf( "%d", &searchKey ) != EOF ) { compare = 0; judge = 0; for( i = 0; i < SIZE; i++ ) // initialize { inputs[i] = 0; } for( i = 0; i < SIZE/5; i++ ) { leaves[i] = -1; branches[i] = -1; } i = 0; do { getter = getchar(); if( getter=='(' || getter==' ' || getter=='\n' ) { if( getter == '(' ) count++; type = 0; } else if( getter==')' || getter=='-' || ( getter>='0' && getter<='9' ) ) { if( getter==')' || getter=='-' ) { if( getter == ')' ) count--; inputs[i] = getter; type = 0; } else { if( inputs[ i-1 ] == '-' ) { inputs[ i-1 ] = -( getter-'0' ) + .5; i--; } else if( !isInt( inputs[ i-1 ] ) && type ) { if( inputs[ i-1 ] >= 0 ) { inputs[ i-1 ] = ( inputs[ i-1 ] - .5 )*10 + ( getter-'0' ) + .5; } else { inputs[ i-1 ] = ( inputs[ i-1 ] - .5 )*10 - ( getter-'0' ) + .5; } i--; } else { inputs[i] = ( getter-'0' ) + .5; } type = 1; } i++; } } while( i==0 || count>0 ); // 위의 do-while문을 탈출하는 순간 기존 풀이의 세번째 while문까지 처리 끝 inputs[i] = .33; // sentinel key i = 0, j = 0; while( inputs[i] != .33 ) { if( isInt( inputs[i] ) && isInt( inputs[ i-1 ] ) && !isInt( inputs[ i-2 ] ) ) { leaves[j] = i; j++; } i++; } // 위의 while문을 탈출하는 순간 기존 풀이의 네번째 while문까지 처리 끝 length = i; i = 0, j = 0; while(1) { if( inputs[0]==')' && inputs[1]==.33 ) break; // there is no tree if( judge == 1 ) break; for( i = 0; i < length; i++ ) { if( !isInHere( i, leaves ) && !isInHere( i, branches ) ) { if( !isInt( inputs[i] ) ) // it is number { compare += (int)( inputs[i] - .5 ); } else { if( isInt( inputs[i] ) && isInt( inputs[ i-1 ] ) && !isInt( inputs[ i-2 ] ) ) { branches[j] = i; i--; j++; } } } else { if( isInHere( i, leaves ) && compare==searchKey ) // it is leaf and find out value of searchKey { judge = 1; break; } else // it is branch or is leaf and not found value of searchKey { compare -= (int)( inputs[ i-2 ] - .5 ); if( isInHere( i, leaves ) ) pullOut( i, inputs, &length, leaves, branches ); else pullOut( i, inputs, &length, branches, leaves ); i -= 3; } } } } if( judge ) printf("yes\n"); else printf("no\n"); } }

설명은 따로 하지 않겠습니다

지난 풀이(WA)랑 같은 알고리즘이라서 -_-;



pku에서는 AC,
정말 압도적인 코드 길이 ㅋㅋㅋㅋ

그리고 uva에서는 TLE;
뭐임? -_-;