글 읽기 - 파이썬 시간초과 관련 질문

chjwoo123 2년 전 0

파이썬3 기준으로 4%, 파이파이 기준으로 9% 부분에서 시간초과로 문제를 해결할 수 없습니다.

아래 코드에서 어느 부분을 고쳐야 2247번 문제를 풀 수 있을까요...

import math
import sys

divisors = []
SOD = 0
n = int(sys.stdin.readline())

def get_divisor(n):
    length = int(math.sqrt(n)) + 1
    for i in range(1, length):
        if n % i == 0:
            divisors.append(i)
            divisors.append(n//i)
            if i == 1:
                pass
            else:
                if i == n//i:
                    divisors.remove(i)
    
    divisors.sort()

def get_SOD(n):
    global SOD
    global divisors
    SOD = 0
    get_divisor(n)
    divisors.remove(1)
    divisors.remove(n)
    for j in divisors:
        SOD += j
    divisors = []
    return SOD

get_SOD(n)

result = 0
for i in range(1, n+1):
    result += get_SOD(i)

print(result % 1000000)

andyjung2104 2년 전 1

다른 방법도 있겠지만, 저같은 경우에는 n//i가 같은 i들은 한번에 계산하면 시간복잡도를 줄였어요

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

문제

문제

출처

ICPC

파이썬 시간초과 관련 질문

chjwoo123 2년 전 0

andyjung2104 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말