[Silver IV] 시간초과 - 11332

[문제 위치]

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

[문제 풀이]

문자열을 파악하여 초과여부를 확인하는 문제이다.

중요한 점은 숫자를 만든 다음 비교하려고 하면 오버 플로우가 생길 수 있다는 것이다.

 

따라서 최댓값에서 감소시키면서 알아본다는 느낌으로 하는 것이 중요하다.

#include <iostream>
#include <string>
#include <cmath>

using namespace std;

bool isTLE(const string& complexity, long long N, long long T, long long L) {
    const long long LIMIT = 100000000LL * L;

    if (complexity == "O(N)") {
        if (N > LIMIT / T) return true;
    } 
    else if (complexity == "O(N^2)") {
        if (N > sqrt(LIMIT / T)) return true; // N^2 > LIMIT/T -> N > sqrt(LIMIT/T)
    } 
    else if (complexity == "O(N^3)") {
        if (N > cbrt(LIMIT / T)) return true; // N^3 > LIMIT/T -> N > cbrt(LIMIT/T)
    } 
    else if (complexity == "O(2^N)") {
        long long maxN = 0;
        long long value = 1;
        while (value <= LIMIT / T) {
            maxN++;
            value *= 2;
        }
        if (N >= maxN) return true;
    } 
    else if (complexity == "O(N!)") {
        long long factorial = 1, i = 1;
        while (factorial <= LIMIT / T) {
            i++;
            factorial *= i;
            if (i > N) break;
        }
        if (N >= i) return true;
    }

    return false;
}

int main() {
    int C;
    cin >> C;

    while (C--) {
        string complexity;
        long long N, T, L;
        cin >> complexity >> N >> T >> L;

        if (isTLE(complexity, N, T, L)) {
            cout << "TLE!" << endl;
        } else {
            cout << "May Pass." << endl;
        }
    }

    return 0;
}