[ 백준 ] 11332 / 시간초과

9453 단어 psbojboj

# Appreciation

/*
 * Problem :: 11332 / 시간초과
 *
 * Kind :: Simulation
 *
 * Insight
 * - 시간복잡도 <= L*10^8 이어야 시간초과가 나지 않는다
 *   + O(N) -> N*T <= L*10^8
 *     O(N^2) -> N*N*T <= L*10^8
 *     O(N^3) -> N*N*N*T <= L*10^8
 *     O(2^N) -> 2^N*T <= L*10^8
 *     O(N!) -> N!*T <= L*10^8
 *     각 경우마다 시간복잡도를 계산해서 제한시간과 비교해주면 된다
 *     # 역시나 Overflow 가 문제인데...
 *       그래서 그냥 double 자료형을 사용했다
 *       max(N)=10^6, max(T,L)=10 인데
 *       12자리 이상의 정밀도를 보존하는 double 자료형이라면 괜찮을 것 같았다
 *       -> 그래서 N, T, L 모두 double 자료형으로 값을 받았다
 *
 * Point
 * - 2^N 이나 N! 은 N, N^2, N^3 과 달리
 *   N 이 조금만 커져도 상상을 초월하는 큰 수가 된다
 *   그래서 계산중간에 L*10^8 을 넘으면 불가능하다고 판단했었다
 *   + 곰곰이 생각해보니 log2 를 활용하면 좀더 간단히 판별할 수 있다
 *     2^N*T <= L*10*8
 *     2^N <= L*10*8/T
 *     N <= log2(L*10*8/T)
 *     # <cmath> 의 log2 를 사용해주자
 *   + 마찬가지로 팩토리얼도 직접 계산할 필요없이
 *     팩토리얼로 계산한 로그를 얻으면(정수부분만) 좀더 간단히 판별할 수 있다
 *     # 함수이름을 logf 로 하고 싶었는데 <cmath> 에 이미 존재해서 충돌이 계속 일어났다
 *       그래서 log_f 로 선언하였따
 *       -> 불편...
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <cmath>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
double log_f(double n);


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int C; cin >> C;

    while (C--) {
        string S; double N, T, L;
        cin >> S >> N >> T >> L;

        // Process
        L *= 100'000'000;
        L /= T; /* 제한시간 */

        bool isPossible = true;
        if (S == "O(N)" && N > L) { isPossible = false; }
        if (S == "O(N^2)" && N*N > L) { isPossible = false; }
        if (S == "O(N^3)" && N*N*N > L) { isPossible = false; }
        if (S == "O(2^N)" && N > log2(L)) { isPossible = false; }
        if (S == "O(N!)" && N > log_f(L)) { isPossible = false; }

        // Control : Output
        cout << ((isPossible) ? "May Pass." : "TLE!") << endl;
    }
}

// Helper Functions
double log_f(double n)
/* 정수부분의 팩토리얼 로그를 구하는 함수 */
{
    int i = 1; double v = 1;
    while ((v *= ++i) <= n);
    return i-1;
}

좋은 웹페이지 즐겨찾기