글 읽기 - 4673번 파이썬 시간초과 질문드립니다.

ssr226 3년 전 0

제가 아직 초보라서 풀 수 있는 대로 일단 풀어봤습니다. 그런데 프로그램에서는 맞는 것 같은데 시간초과가 됩니다ㅜㅜ 시간에 맞추려면 아예 다른 방식으로 다시 풀어봐야 할까요?

def self_number():
    for x in range(1,10001):
        for y in range(1, 10002):
            hap = y
            for z in str(y):
                hap += int(z)
            if hap == x:
                break
            elif y == 10001:
                print(x)
                break
self_number()

djm03178 3년 전 0

이 코드에서 안쪽 루프가 도는 횟수는 54771928번인데, 안타깝게도 Python 3는 너무 너무 느려서 이 정도 횟수의 연산을 시간 내에 처리하지 못합니다. 다만 PyPy3를 사용하면 약 3.7초에 통과할 수 있습니다.

시간을 획기적으로 줄이고자 한다면 각 수에 대한 생성자가 존재하는지를 확인하는 대신에 각 수가 누구에 대한 생성자가 되는지를 계산해서 만들어지지 않은 수들을 나중에 몰아서 출력하는 방법이 있습니다.

ssr226 3년 전 0

감사합니다! 알려주신대로 곰곰히 생각해보고 다시 도전해봐야겠네요!

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

문제

문제

출처

ICPC

4673번 파이썬 시간초과 질문드립니다.

ssr226 3년 전 0

djm03178 3년 전 0

ssr226 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말