백준 11332 시간초과 문제 풀이
백준 11332 시간초과 문제 풀이
백준 온라인 저지, 11332번: 시간초과
도입
주어진 시간 복잡도 $O(?)$ 식을 그대로 연산하여 제한 시간 내에 해당 시간 복잡도 알고리즘으로 통과할 수 있는지 여부를 출력한다.
풀어보기
다른 시간 복잡도 케이스와는 달리 $O(N!)$은 팩토리얼 값을 직접 계산해야 한다. 문제는 팩토리얼 연산은 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
하지만 그 값을 출력하는 것이 아니라 시간 초과를 여부를 판단하는 것이 목표이므로, 큰 수에 대해서는 팩토리얼 연산을 조기에 중단하고 시간 초과로 반환하는 방법을 사용할 수 있다.
팩토리얼 연산 조기 중단
문제에서는 1초에 $10^8$번의 연산을 수행할 수 있다고 가정한다. 따라서 다음과 같이 조기에 종료시킬 수 있다.
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