ACM(알고리즘 대회) 문제 데이터 베이스에서 대회 준비한다고 골라서 푼 문제... ^^;;;

 ACM 대회 준비를 위해 4문제 정도를 골라 풀었습니다만, 테스트를 위해 올렸을 때 Accept는 하나밖에 못받았습니다. ㅜ_ㅜ.. 뭐가 문제가 있던 것인지.... 대회는 끝났지만 그래도 푼 김에 소스를 한번 올려봅니다. 하드에 썩히기에는 왠지 아까워서 ^^;;;
 
 그렇다고 풀이가 상당이 완성도가 높거나 멋지거나 하진 않습니다. Accept가 안된걸 보면 무슨 문제가 있거나 오답인 것이겠지요 ^^;;;그러고 보니 올리기가 좀 부끄럽군요. (* ㅡ_ㅡ*)

 ACM 문제 데이터베이스는 http://icpcres.ecs.baylor.edu/onlinejudge/index.php 사이트에서 보실 수 있습니다. 그럼 아래에 코드 나갑니다. ^^;;;;

* 100번 문제에 대한 코드 보기

// ACM.cpp : Defines the entry point for the console application. // #include <stdio.h> #define MAX 1000000 int g_viMax[ MAX + 1 ]; int main( void ) { int iStart; int iEnd; int i; int iProcess; unsigned long j; int iMax; // 초기화 for( i = 0 ; i < MAX + 1 ; i++ ) { g_viMax[ i ] = 0; } // 1 부터 MAX 까지 계산한다. for( i = 1 ; i <= MAX ; i++ ) { iProcess = 0; j = i; while( 1 ) { iProcess++; if( j == 1 ) { g_viMax[ i ] = iProcess; //printf( "%d\n", i ); break; } if( j % 2 == 1 ) { j = j * 3 + 1; } else { j = j / 2; } if( ( j < MAX ) && ( g_viMax[ j ] != 0 ) ) { iProcess += g_viMax[ j ]; g_viMax[ i ] = iProcess; break; } } } while( scanf( "%d %d", &iStart, &iEnd ) == 2 ) { printf( "%d %d ", iStart, iEnd ); if( iStart > iEnd ) { i = iStart; iStart = iEnd; iEnd = i; } iMax = 0; // 일일이 다 찾는다. for( i = iStart ; i <= iEnd ; i++ ) { if( g_viMax[ i ] > iMax ) { iMax = g_viMax[ i ]; } } printf( "%d\n", iMax ); } return 0; }

* 121번 문제에 대한 코드 보기

#include <stdio.h> #include <math.h> int main( void ) { float fD1; float fD2; int iGrid1; int iGrid2; int iGridMax; int iSkew1; int iSkew2; int iSkewMax1; int iSkewMax2; int iSkewHeight; // 입력 while( 1 ) { if( scanf( "%f %f", &fD1, &fD2 ) != 2 ) { break; } // Grid의 max 값 iGrid1 = ( int ) fD1; iGrid2 = ( int ) fD2; iGridMax = iGrid1 * iGrid2; // Skew의 max1 값 iSkew1 = ( int ) fD1; iSkew2 = ( int ) ( fD1 - 0.5 ); iSkewHeight = ( fD2 - 1 ) / sqrt( 0.75 ); iSkewHeight++; iSkewMax1 = iSkew1 * ( iSkewHeight / 2 ); iSkewMax1 += iSkew2 * ( iSkewHeight / 2 ); if( iSkewHeight % 2 == 1 ) { iSkewMax1 += iSkew1; } // Skew의 max2 값 iSkew1 = ( int ) fD2; iSkew2 = ( int ) ( fD2 - 0.5 ); iSkewHeight = ( fD1 - 1 ) / sqrt( 0.75 ); iSkewHeight++; iSkewMax2 = iSkew1 * ( iSkewHeight / 2 ); iSkewMax2 += iSkew2 * ( iSkewHeight / 2 ); if( iSkewHeight % 2 == 1 ) { iSkewMax2 += iSkew1; } if( ( iGridMax >= iSkewMax1 ) && ( iGridMax >= iSkewMax2 ) ) { printf( "%d grid\n", iGridMax ); } else { if( iSkewMax1 > iSkewMax2 ) { printf( "%d skew\n", iSkewMax1 ); } else { printf( "%d skew\n", iSkewMax2 ); } } } return 1; }

*151번 문제에 대한 코드 보기

#include <stdio.h> int g_viArray[ 120 ]; int main( int argc, char** argv ) { int i; int iNum; int k; int iIndex; int j; while( 1 ) { scanf( "%d", &iNum ); if( iNum == 0 ) { break; } for( k = 2 ; k < 100 ; k++ ) { // 초기화 for( i = 0 ; i < 120 ; i++ ) { g_viArray[ i ] = 0; g_viArray[ 0 ] = 1; g_viArray[ 1 ] = 1; } i = 1; while( 1 ) { for( j = 0 ; j < k ; ) { if( g_viArray[ i % ( iNum + 1 ) ] == 0 ) { j++; } i++; } iIndex = ( i - 1 ) % ( iNum + 1 ); g_viArray[ iIndex ] = 1; //printf( "%d ", iIndex ); for( j = 0 ; j <= iNum ; j++ ) { if( g_viArray[ j ] == 0 ) { break; } } if( j > iNum ) { break; } } if( iIndex == 13 ) { goto END; } } END: printf( "%d\n", k ); } return 1; }

* 821번 문제에 대한 코드 보기

// ACM.cpp : Defines the entry point for the console application. // #include <stdio.h> #define MAXPAIR 1000000 #define MAXNUMBER 100 double g_vdOutput[ MAXPAIR ]; int g_iOutputCount; int g_viPair[ MAXPAIR ][ 2 ]; int g_iPairCount; int g_viPath[ MAXPAIR ]; int g_iPathCount; int g_viNode[ MAXPAIR ]; int g_iNodeCount; int g_vviShortestPath[ MAXNUMBER + 1 ][ MAXNUMBER + 1 ]; int ShortestPath( int iStart, int iEnd ); /** 노드가 Node List에 있는가? */ bool IsNotInNodeList( int iNode ) { int i; for( i = 0 ; i < g_iNodeCount ; i++ ) { if( g_viNode[ i ] == iNode ) { return false; } } return true; } int main( void ) { int i; int j; int iTotalLength; int iTemp; bool bOK; g_iOutputCount = 0; // 초기화 for( i = 0 ; i < MAXPAIR ; i++ ) { g_viPair[ i ][ 0 ] = 0; g_viPair[ i ][ 1 ] = 0; g_viPath[ i ] = 0; } while( 1 ) { // 초기화 for( i = 0 ; i <= MAXNUMBER ; i++ ) { for( j = 0 ; j <= MAXNUMBER ; j++ ) { g_vviShortestPath[ i ][ j ] = 0; } } // 입력받기 j = 0; g_iNodeCount = 0; bOK = false; while( scanf( "%d %d", &( g_viPair[ j ][ 0 ] ), &( g_viPair[ j ][ 1 ] ) ) == 2 ) { bOK = true; // 만약 노드가 처음 등장한 것이면 Node List에 넣는다. if( ( IsNotInNodeList( g_viPair[ j ][ 0 ] ) == true ) && ( g_viPair[ j ][ 0 ] != 0 ) ) { g_viNode[ g_iNodeCount ] = g_viPair[ j ][ 0 ]; g_iNodeCount++; } // 만약 노드가 처음 등장한 것이면 Node List에 넣는다. if( ( IsNotInNodeList( g_viPair[ j ][ 1 ] ) == true ) && ( g_viPair[ j ][ 1 ] != 0 ) ) { g_viNode[ g_iNodeCount ] = g_viPair[ j ][ 1 ]; g_iNodeCount++; } // 둘다 0이면 종료 if( ( j == 0 ) && ( ( g_viPair[ 0 ][ 1 ] == 0 ) || ( g_viPair[ 0 ][ 0 ] == 0 ) ) ) { goto END; } else if( ( g_viPair[ j ][ 1 ] == 0 ) || ( g_viPair[ j ][ 0 ] == 0 ) ) { break; } j++; } if( bOK == false ) { goto END; } g_iPairCount = j; iTotalLength = 0; // 각 점에 대해서 다른 노드로 가는 최단거리 찾기 for( i = 0 ; i < g_iNodeCount ; i++ ) { g_iPathCount = 1; g_viPath[ 0 ] = g_viNode[ i ]; for( j = 0 ; j < g_iNodeCount ; j++ ) { if( i != j ) { if( g_vviShortestPath[ g_viPath[ 0 ] ][ g_viNode[ j ] ] == 0 ) { iTemp = ShortestPath( g_viPath[ 0 ], g_viNode[ j ] ); g_vviShortestPath[ g_viPath[ 0 ] ][ g_viNode[ j ] ] = iTemp; iTotalLength += iTemp; } else { iTotalLength += g_vviShortestPath[ g_viPath[ 0 ] ][ g_viNode[ j ] ]; } } } } g_vdOutput[ g_iOutputCount ] = ( double ) iTotalLength / ( g_iNodeCount * ( g_iNodeCount - 1 ) ); printf( "Case %d: average length between pages = %.3f clicks \n", g_iOutputCount + 1, g_vdOutput[ g_iOutputCount ] ); g_iOutputCount++; } END: return 1; } /** 노드가 Path에 있는가? */ bool IsNotInPathList( int iNode ) { int i; for( i = 0 ; i < g_iPathCount ; i++ ) { if( g_viPath[ i ] == iNode ) { return false; } } return true; } /** 최단거리를 찾는 재귀함수 */ int ShortestPath( int iStart, int iEnd ) { int iShortest; int iTemp; int i; int iTempStart; iShortest = 200; iTempStart = iStart; // 바로 갈수 있는가? for( i = 0 ; i < g_iPairCount ; i++ ) { if( ( g_viPair[ i ][ 0 ] == iTempStart ) && ( g_viPair[ i ][ 1 ] == iEnd ) ) { return g_iPathCount; } } // 바로 못간다면 가능한 쪽으로 다 가본다. for( i = 0 ; i < g_iPairCount ; i++ ) { // 노드를 찾아서 그쪽으로 간다. if( ( g_viPair[ i ][ 0 ] == iTempStart ) && ( IsNotInPathList( g_viPair[ i ][ 1 ] ) == true ) ) { g_viPath[ g_iPathCount ] = g_viPair[ i ][ 1 ]; g_iPathCount++; // 최단거리 갱신 iTemp = ShortestPath( g_viPair[ i ][ 1 ], iEnd ); if( iTemp < iShortest ) { iShortest = iTemp; } g_iPathCount--; } } return iShortest; }