글 읽기 - 파이썬 왜 시간초과나죠 ..?

thdruddyd21 3년 전 0

조건문 연산들 다 O(1)이고 비교도 최소화했다고 생각했는데 왜 Python3로 채점하면 초과하는지 모르겠습니다 ..

import math
N = int(input())
for _ in range(N):
    t = input().split()
    t[1] = int(t[1])
    t[2] = int(t[2])
    t[3] = int(t[3])
    if t[0][2] == 'N':
        if t[0][3] == ')': # n
            if t[3] * 10**8 >= t[2] * t[1]:
                S = True
            else:
                S = False
        elif t[0][3] == '^':
            if t[0][4] == '2': # n^2
                if t[3] * 10**8 >= t[2] * t[1]**2:
                    S = True
                else:
                    S = False
            else: # n^3
                if t[3] * 10**8 >= t[2] * t[1]**3:
                    S = True
                else:
                    S = False
        elif t[0][3] == '!':
            if t[3] * 10**8 >= t[2] * math.factorial(t[1]):
                S = True
            else:
                S = False
    else:
        if t[3] * 10 ** 8 >= t[2] * 2**t[1]:
            S = True
        else:
            S = False
    if S:
        print("May Pass.")
    else:
        print("TLE!")

djm03178 3년 전 1

math.factorial이 O(1)이 아닙니다. factorial의 결과 자릿수가 아주 클 수 있고, 계산 시간 복잡도는 그 자릿수보다도 더 큽니다.

thdruddyd21 3년 전 0

하지만 python3으로 아주 빨리 통과하신 분들 코드 보면 math.factorial함수를 쓰셨더라고요..

djm03178 3년 전 1

혹시 어떤 코드인지 하나만 보여주실 수 있나요? 제 생각엔 크기가 큰 경우를 예외로 처리하는 코드가 있는 게 아니고서는 어려울 것 같아서 그렇습니다. 20 이상만 예외로 처리해준다면 문제 없습니다.

djm03178 3년 전 1

http://boj.kr/eb015be977e8407d... 와 같이 math.factorial(500000)으로도 상당한 시간이 걸리며, 100만을 사용할시 TLE가 납니다.

thdruddyd21 3년 전 0

아.. 죄송합니다 제가 잘못 본 것 같습니다.. 예외처리해주니 빠르게 돌아가네요 감사합니다!

알려주신 시간 체크 방법이 되게 유용한거같습니다 ! 저 코드는 2400ms의 시간이 소요되는데, 모든 테스트케이스를 통과한 시간인가요?

djm03178 3년 전 1

시간은 모든 케이스 각각에 대해서 걸린 시간의 최댓값입니다. 어차피 저 문제는 테스트가 한 개뿐입니다.

thdruddyd21 3년 전 0

저 문제의 시간 제한은 1초인데 2.5초가 걸린 테스트케이스가 통과한 이유가 궁금합니다 !

djm03178 3년 전 1

언어별 시간 보너스 때문입니다.

https://www.acmicpc.net/help/l...

댓글을 작성하려면 로그인해야 합니다.