(C)백준 11332번 시간초과 C언어 풀이

방학기간 첫번째 문제.시간 복잡도 개념 문제이다.

#include <stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#define cons 100000000
int factorial(int n){
    int fact=1;
    for(int i=n;i>0;i--)
        fact*=i;
    return fact;
}
int main(void){
    int num;
    scanf("%d ",&num);
    for (int i=0;i<num;i++)
    {
        char s[10]; int n=0,t=0,l=0,time=0;
        scanf("%s %d %d %d",s,&n,&t,&l);
        if(!strcmp(s, "O(N)"))
        {
            time=n*t;
            if(time<=l*cons)
                printf("May Pass.\n");
            else
                printf("TLE!\n");
        }
        else if(!strcmp(s, "O(N^2)"))
        {
            time=pow(n, 2)*t;
            if(time<=l*cons)
                printf("May Pass.\n");
            else
                printf("TLE!\n");
        }
        else if(!strcmp(s, "O(N^3)"))
        {
            time=pow(n,3)*t;
            if(time<=l*cons)
                printf("May Pass.\n");
            else
                printf("TLE!\n");
        }
        else if(!strcmp(s, "O(2^N)"))
        {
            time=pow(2,n)*t;
            if(time<=l*cons)
                printf("May Pass.\n");
            else
                printf("TLE!\n");
        }
        if(!strcmp(s, "O(N!)"))
        {
            time=factorial(n)*t;
            if(time<=l*cons)
                printf("May Pass.\n");
            else
                printf("TLE!\n");
        }
    }
}

대분이 이 상태에서 막혀서 구글링 중이지 않을까 싶다. 
int를 long long으로 바꿔도 틀린다.
이유는 time=n*t를 하면 time에서 오버플로우가 발생할 수 있기 때문이다.
 
다음과 같이 곱셈이 아닌 나누기를 활용하면 오버플로우가 생기는 것을 방지할 수 있다.
수학적으로 생각해 보면 아무런 문제가 없지만, 코드를 짤 때에는 주의를 해줘야 됨을 알 수 있다.

#define cons 100000000LL

int main(void){
    int num;
    scanf("%d ",&num);
    for (int i=0;i<num;i++)
    {
        char s[10]; long long int n=0,t=0,l=0,time=0;
        scanf("%s %lld %lld %lld",s,&n,&t,&l);
        l *= cons; //l should be converted to operations
        if(!strcmp(s, "O(N)"))
        {
            if(n > l / t)
            {
                printf("TLE!\n");
                continue;
            }
            
            
            printf("May Pass.\n");
            
        }
        else if(!strcmp(s, "O(N^2)"))
        {
            if(n > sqrt((double)l / t))
            {
                printf("TLE!\n");
                continue;
            }
            printf("May Pass.\n");
            
        }
        else if(!strcmp(s, "O(N^3)"))
        {
            if(n > cbrt((double)l / t))
            {
                printf("TLE!\n");
                continue;
            }
            printf("May Pass.\n");
            
        }
        else if(!strcmp(s, "O(2^N)"))
        {
            if(n > log2((double)l / t))
            {
                printf("TLE!\n");
                continue;
            }
            
            printf("May Pass.\n");
        }
        else if(!strcmp(s, "O(N!)"))
        {
            
            long long fact = 1;
            for(int j=2; j<=n; j++){
                fact *= j;
                if (fact > l / t) {
                    printf("TLE!\n");
                    break;
                }
                
                }
            if (fact <= l / t)
                printf("May Pass.\n");
        }
    }
}

오늘의 핵심 포인트

오버플로우를 주의하자