[11332번] 시간초과

문제 출처 :

https://www.acmicpc.net/problem/11332

알고리즘 분석 :

문제 해결에 필요한 사항

1. 구현

실제로 시간 복잡도를 계산해보는 문제이다.

테스트케이스와 n이 어떻게 동작하는지 생각해보면 문제를 해결할 수 있다.

이때 모든 수를 처리한 후 TLE인지 파악하면 long long 범위마저 벗어나므로 계산하며 TLE인지 파악해보자.

소스 코드 : 

#include <iostream>
#include <string>
#include <cstdio>
 
typedef long long ll;
 
using namespace std;
 
int main()
{
    long long n;
    cin >> n;
    
    while (n--)
    {
        string str;
        cin >> str;
 
        long long n, tc, l;
        cin >> n >> tc >> l;
 
        long long ans = 0;
        if (str == "O(N)")
        {
            ans = tc * n;
            if (ans > l *(ll)100000000)
            {
                cout << "TLE!" << endl;
                continue;
            }
        }
        else if (str == "O(2^N)")
        {
            bool chk = true;
            ans = tc;
            for (int i = 1; i <= n; i++)
            {
                ans *= 2;
                if (ans > l * (ll)100000000)
                {
                    cout << "TLE!" << endl;
                    chk = false;
                    break;
                }
            }
            if (!chk)
                continue;
        }
        else if (str == "O(N!)")
        {
            bool chk = true;
            ans = tc;
            for (int i = 1; i <= n; i++)
            {
                ans *= i;
 
                if (ans > l *(ll)100000000)
                {
                    cout << "TLE!" << endl;
                    chk = false;
                    break;
                }
            }
            if (!chk)
                continue;
        }
 
        else if (str == "O(N^2)")
        {
            ans = tc*n*n;
            if (ans > l *(ll)100000000)
            {
                cout << "TLE!" << endl;
                continue;
            }
        }
        else if (str == "O(N^3)")
        {
            ans = tc*n;
            if (ans > l * (ll)100000000)
            {
                cout << "TLE!" << endl;
                continue;
            }
            ans *= n;
            if (ans > l * (ll)100000000)
            {
                cout << "TLE!" << endl;
                continue;
            }
            ans *= n;
            if (ans > l * (ll)100000000)
            {
                cout << "TLE!" << endl;
                continue;
            }
        }
 
        cout << "May Pass." << endl;
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>