[UVA] UVA 100 문제풀이

UVA 라는 사이트를 알게 됐다.

알고리즘 문제들이 있고, 소스를 올려서 본인의 랭킹같은거도 나온다.

재미삼아 제일 첫번째 100번 문제를 풀어봤는데.. 그리 어렵지 않았다.

include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
#define INPUT_SIZE 10000
 
int cycleLength(int n, int len)
{
        len++;
        if(n == 1) return len;
 
        if( (n % 2) == 0 ) n = n / 2;
        else n = 3 * n + 1;
        return cycleLength(n, len);
 
}
 
int main() {
 
        char sLine[INPUT_SIZE];
        int i;
        char delim[] = "' '";
        int value1, value2;
        int small, large, length, temp, cycle_length;
 
        while(fgets(sLine, INPUT_SIZE, stdin) != NULL)
        {
                cycle_length = 0;
                value1 = atoi(strtok(sLine, delim));
                value2 = atoi(strtok(NULL, delim));
                if(value1 > value2){
                        small = value2;
                        large = value1;
                }
                else{
                        small = value1;
                        large = value2;
                }
                length = large - small+1;
                for(i = small; i < small + length; i++)
                {
                        temp = cycleLength(i, 0);
                        printf("i : %d, return : %d", i, temp);
                        if( cycle_length < temp ) cycle_length = temp;
                }
                printf("%d %d %d\n", value1, value2, cycle_length);
        }
        return 0;
}

올려놓고 보니 수행시간이 나오고 랭킹이 나왔다. 수행시간 1.150 에 7609등 ㅎㅎ;
음 순위권들을 보니 다들 수행시간이 0이다.

수행시간을 절약하는 방법이 머가 있을까 고민해서 좀 개선해 본 소스..
재귀함수를 반복문으로 바꾸고, 나누기나 곱하기 연산을 쉬프트를 이용해봤다.

그랬더니 0.880수행시간에 순위가 6360등;;  아마도 순위권인 사람들은 반복문도 안돌리고, 출력값을 수식으로 일반화 시킨듯 한데.. 어렵군;

 

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
#define INPUT_SIZE 100
 
int main(){
 
        char sLine[INPUT_SIZE];
        int i;
        char delim[] = "' '";
        int value1, value2;
        int small, large, length, temp, cycle_length;
        int len, num;
 
        while(fgets(sLine, INPUT_SIZE, stdin) != NULL)
        {
                cycle_length = 0;
                value1 = atoi(strtok(sLine, delim));
                value2 = atoi(strtok(NULL, delim));
                if(value1 > value2){
                        small = value2;
                        large = value1;
                }
                else{
                        small = value1;
                        large = value2;
                }
                for(i = small; i <= large; i++)
                {
                        len = 1;
                        num = i;
                        while(num != 1)
                        {
                                if( (num & 0x01) == 0 )
                                        num = num >> 1;
                                else
                                        num = ((num << 1) + num) + 1;
                                len++;
                        }
                        if( cycle_length < len ) cycle_length = len;
                }
                printf("%d %d %d\n", value1, value2, cycle_length);
        }
        return 0;
}