[백준/Python] (S4) 시간초과 - 11332

Baekjoon Online Judge의 11332번 시간초과 문제의 Python 풀이입니다.

11332번: 시간초과

💻코드

import math
C = int(input())
for _ in range(C):
    complexity, *params = input().split()
    max_input_size, test_count, time_limit = map(int, params)

    if complexity == 'O(N)':
        operations = max_input_size
    elif complexity == 'O(N^2)':
        operations = max_input_size ** 2
    elif complexity == 'O(N^3)':
        operations = max_input_size ** 3
    elif complexity == 'O(2^N)':
        operations = 2 ** max_input_size
    else:  # complexity == 'O(N!)'
        if max_input_size > 12:  # 12보다 크면 무조건 TLE
            print("TLE!")
            continue
        operations = math.factorial(max_input_size)

    if operations * test_count <= 10**8 * time_limit:
        print("May Pass.")
    else:
        print("TLE!")

🧠풀이

이 문제는 입력받은 복잡도와 N, T, L 값에 따라 최대 수행 가능 연산 수를 계산하고, 이를 주어진 시간 내에 수행할 수 있는지 여부를 판단한다. 시간 복잡도가 각기 다른 계산식을 따르므로, 각 경우에 맞게 연산 횟수를 계산하고 이를 제한된 시간과 비교하여 "May Pass." 또는 "TLE!"를 출력한다.

단순히 팩토리얼만 사용하면 시간초과가 난다. 팩토리얼이 13부터는 10^9보다 커져 무조건 TLE라는 점을 고려해야한다.

🤔느낀 점

굳