KOI 2017 - 한국정보올림피아드 초등부

1. 딱지치기 (BOJ 14696번)

어린이 A와 B의 그림을 4,3,2,1 그림에 맞게 cnt배열을 증가시켜준다음, 별에 해당하는 부분부터 비교해 가면서 크면 답을 출력하고 break, 끝까지 가면 'D'를 출력하게 구현하였다.

#include<stdio.h>
#include<string.h>

int main( void ) {
    int N, iter, val;
    scanf( "%d", &N );
    
    int arr[2][4];
    char result;
    
    for( int n = 0; n < N; n++ ) {
    	memset( arr, 0, sizeof ( arr ) );
        
        for( int i = 0; i < 2; i++ ) {
        	scanf( "%d", &iter );
            for( int j = 0; j < iter; j++ ) {
            	scanf( "%d", &val );
                arr[i][val - 1]++;
            }
        }
        
        result = 'D';
        
        for( int i = 3; i >= 0; i-- ) {
        	if( arr[0][i] > arr[1][i] ) {
            	result = 'A'; break; 
            } else if( arr[0][i] < arr[1][i] ) {
            	result = 'B'; break;
            }
        }
        printf( "%c\n", result );
    }
    
    return 0;
}

 

2. 방배정하기 (BOJ 14697번)

완전 탐색으로 해결하였다.

- N명이 있을 때 각 방을 배정할 수 있는 한계가 있다.
- 0부터 그 한계까지 각 방별로 반복문을 중첩한 뒤, (N - 현재 배정 방 인원) 을 마지막 방 인원 수로 나눈 나머지가 0이 될 경우 가능하다고 판단.

#include<stdio.h>

int main( void ) {
	// 방 인원 수 받을 배열 선언
    int arr[3], N;
    scanf( "%d %d %d %d", &arr[0], &arr[1], &arr[2], &N ); // 첫 번째 인원수 제외
    
    for( int i = 0; N - i*arr[0] >= 0; i++ ) {
    	// 두 번째 인원수 제외
        for( int j = 0; N - (i*arr[0] + j*arr[1]) >= 0; j++ ) {
        	// 세 번째 인원수로 나눈 나머지가 0일 경우 '가능'
            if( (N - (arr[0] * i + arr[1] * j)) % arr[2] == 0 ) {
            	printf ( "1\n" ); return 0;
            }
        }
    }
    // 실패
    printf( "0\n" );
    return 0;
}

 

 

3. 서울에서 경산까지 (BOJ 14863번)

문제를 풀기 전에 생각해낸 풀이의 공간복잡도와 시간복잡도를 고려할 수 있어야하는데, 아직은 생각나면 바로 코딩하고, 틀렸다는 결과를 보고나서야 원인을 분석하게 된다.

처음에는 완전 탐색으로 접근을 했다.

#include<stdio.h>

int walk[100][2]; // 시간, 모금액 - 도보 
int cycle[100][2]; // 시간, 모금액 - 자전거
int N, K, Max;

void go( int cur, int time, int Sum ) {
	if ( time > K ) return; 
    if ( cur == N ) {
    	Max = Max < Sum ? Sum : Max; return; 
    }
    go( cur + 1, time + walk[cur][0], Sum + walk[cur][1] );
    go ( cur + 1, time + cycle[cur][0], Sum + cycle[cur][1] );
}

int main( void ) {
	scanf ( "%d %d", &N, &K ); 
    for( int n = 0; n < N; n++ )
    	scanf ( "%d %d %d %d", &walk[n][0], &walk[n][1], &cycle[n][0], &cycle[n][1] );
    
    go ( 0, 0, 0 );
    printf( "%d\n", Max );
    return 0;
}

그런데 이렇게 풀 경우 시간 복잡도가 O(2^N)이 되는데, N의 범위가 100까지라서 매우 오래걸린다.

그래서 DP로 접근했다.

#include<stdio.h>
#include<string.h>

#define max(a,b) ((a)>(b)) ? (a) : (b)
#define IMPOSSIBLE -987654321

int dp[100][100001];
int walk[100][2]; // 시간, 모금액 - 도보 
int cycle[100][2]; // 시간, 모금액 - 자전거

int N, K;
int go( int cur, int timeLeft ) {
	if ( cur == N ) return 0;
    if ( timeLeft <= 0 ) return IMPOSSIBLE; 
    
    int& ret = dp[cur][timeLeft]; 
    if( ret != -1 ) return ret; 
    
    ret = IMPOSSIBLE; 
    if( timeLeft - walk[cur][0] >= 0 && go ( cur + 1, timeLeft - walk[cur][0] ) != IMPOSSIBLE ) 
        ret = max( ret, go( cur + 1, timeLeft - walk[cur][0] ) + walk[cur][1] );
    if( timeLeft - cycle[cur][0] >= 0 && go ( cur + 1, timeLeft - cycle[cur][0] ) != IMPOSSIBLE )
    	ret = max( ret, go( cur + 1, timeLeft - cycle[cur][0] ) + cycle[cur][1] ); 
    
    return ret;
}
        
int main( void ) { 
	scanf( "%d %d", &N, &K ); 
    memset( dp, -1, sizeof ( dp ) ); 
    
    for( int n = 0; n < N; n++ )
    	scanf ( "%d %d %d %d", &walk[n][0], &walk[n][1], &cycle[n][0], &cycle[n][1] ); 
        
    printf ( "%d\n", go ( 0, K ) ); 
    return 0; 
}

백준을 기준으로 이렇게 풀면 메모리 40180KB에 시간이 104ms가 걸린다.
DP 테이블을 배열로 잡았기 때문에 공간 복잡도는 O(N+K), 시간 복잡도는 이렇게 DFS로 타고 들어갈 경우 어떻게 구하는지 아직 모른다...(아시는 분은 댓글에 남겨주세요!)

여기서 메모리를 아끼면서 동시에 시간도 줄일 수 있는 방법을 고민하다가 다음과 같이 구현했다.

#include<stdio.h>
#include<string.h>

#define Max(a,b) ((a)>(b)) ? (a) : (b)

int dp[2][100001];
int walk[101][2]; // 시간, 모금액 - 도보
int cycle[101][2]; // 시간, 모금액 - 자전거
int N, K;

int main( void ) {
	int k, cur, prev, maxV = 0;
    scanf( "%d %d", &N, &K ); 
    
    for( int n = 1; n <= N; n++ ) 
    	scanf ( "%d %d %d %d", &walk[n][0], &walk[n][1], &cycle[n][0], &cycle[n][1] ); 
    
    dp[1][walk[1][0]] = walk[1][1];
    dp[1][cycle[1][0]] = Max( dp[1][cycle[1][0]], cycle[1][1] );
    
    for( int n = 2; n <= N; n++ ) {
    	cur = n & 1;
        prev = (n - 1) & 1; 
        memset( dp[cur], 0, sizeof ( dp[cur] ) ); 
        
        for( k = walk[n][0]; k <= K; k++ ) {
        	if ( dp[prev][k - walk[n][0]] )
            	dp[cur][k] = Max( dp[cur][k], dp[prev][k - walk[n][0]] + walk[n][1] );
        }
        
        for( k = cycle[n][0]; k <= K; k++ ) {
        	if ( dp[prev][k - cycle[n][0]] )
            	dp[cur][k] = Max( dp[cur][k], dp[prev][k - cycle[n][0]] + cycle[n][1] );
        }
    }
        
    cur = N & 1;
        
    for( k = 1; k <= K; k++ ) { 
    	maxV = Max( maxV, dp[cur][k] );
    }
    printf( "%d\n", maxV );
        
    return 0;
}

이 문제에서 DP를 구할 때 필요한 것은 바로 전 경로에서 구했던 DP와, 현재 구하고 있는 DP 이렇게 두 줄만 필요하다. 따라서 논리연산자 &를 활용해서 현재 cur와 이전 prev를 쉽게 이동할 수 있도록 구현했다. (짝수, 홀수로 접근)

 

4. 줄서기 (BOJ 14864번)

처음에는 위상정렬로 접근을 해서 풀었다.
(X, Y)를 받아서 X에서 뻗어 나가는 수를 인덱스로 사용해서 해당 학생의 값을 찾아내었다.

Ex) 테케 예시 1번
학생 1번의 idx값이 2가 나오므로, 배열 A = {1, 2, 3, 4, 5}에서 A[2]인 3이라는 값을 가지게 된다.
다음 학생 2번의 idx값은 0이고, 배열 A = {1, 2, 4, 5}에서 A[0]인 1이라는 값을 가짐.
다음 학생 3번의 idx값은 2이고, 배열 A = {2, 4, 5}에서 A[2]인 5라는 값을 가짐
쭉...

이렇게 풀었더니 대략 10,000KB에 1.1초가 걸렸다.
고민하다가, 이번에는 뻗어 나가는 수는 +, 들어오는 수는 -로 계산한 뒤에, 각 학생 번호를 더해주었다.

Ex) 테케 예시 1번
위의 방법을 고려했을 때 {2,-1,2,0,3}이 나오는데, 여기에 학생 번호를 더해주면
{3,1,5,4,2}가 나온다.

#include<stdio.h>

int list[100001], visited[100001], total;

int main( void ) { 
	int N, M, a, b; 
    scanf( "%d %d", &N, &M );
    
    for( int m = 0; m < M; m++ ) {
    	scanf( "%d %d", &a, &b ); 
        list[a]++; list[b]--;
    }
    
    for( int n = 1; n <= N; n++ ) { 
    	list[n] += n; 
        
        if( list[n] > 0 && !visited[list[n]] ) {
        	total++; 
            visited[list[n]] = 1;
        }
    }
    
    if( total == N ) 
    	for( int n = 1; n <= N; n++ ) 
        	printf ( "%d ", list[n] ); 
    else 
    	printf ( "-1\n" );
    
    return 0;
}

 

느낀점
: 와.. 공부할겸 초등부 올림피아드 풀어봤는데 장난 아니구나.. 라는 것을 깨달음
기본기 닦는데 최고인 듯!