백준 11332 시간초과 문제 풀이
문제 파악하기
주어진 시간 복잡도 O(?) 식을 그대로 연산하여 제한 시간 내에 해당 시간 복잡도 알고리즘으로 통과할 수 있는지 여부를 출력하는 문제입니다.
문제 풀어보기
팩토리얼 연산은 N이 커질 수록 연산 속도가 매우 느려집니다.
다른 시간 복잡도 케이스와는 달리 O(N!)은 실제로 값을 계산해야 하므로 별다른 처리 없이 팩토리얼 연산을 코드 속에 추가하면 시간 초과가 발생할 수 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
from time import time
n = int(input())
res = 1
start = time()
while n > 1:
res *= n
n -= 1
end = time()
print(f'elapsed: {end - start}')
입력 케이스
1
100000
출력 케이스
1
elapsed: 3.121413230895996
하지만 팩토리얼 연산 결과가 108 * 10을 넘는데는 짧은 시간이 소요되므로 팩토리얼 연산 중에 결과값의 시간초과 여부를 평가할 수도 있습니다.
1
2
3
4
5
6
7
8
9
temp = n
n -= 1
while n > 1
pass = temp * t < 1e8.to_i * l
if !pass then break end
temp *= n
n -= 1
end
pass = temp * t < 1e8.to_i * l