글 읽기 - 4948번 시간초과 문제

free0122 1년 전 0

이런거 저런거 다해봤는데도 시간초과가 뜨네요. ㅠㅠ

어떻게 더 빠르게 할까요?

while 1:
    n = int(input())
    if n == 0:
        break
    if n == 1:
        print(1)
        continue
    num = 0
    for i in range(n+1,2*n):
        a = 1
        if i%2 ==0 and i !=2:
            continue
        if i%3 ==0 and i !=3:
            continue
        if i%5 ==0 and i !=5:
            continue
        if i%7 ==0 and i !=7:
            continue
        for ii in range(2,int(i*0.5)+1):
            if i % ii == 0:
                a = 0
                break
        if a:
            num += 1
    print(num)

일단 ii 들어간 for문에 i*(0.5)라 되어있습니다. 에라토스테네스 체가 O(n^1/2)인데 지금 코드는 O(n^2)인거 같습니다. 혹시 몰라서 작성자분이 다른 소수 문제를 푸신게 있나 봤고, 소수구하기 문제 코드가 있길레 봤습니다만, 지금 아예 핵심을 이해하지 못하신거 같습니다. 5700ms 걸릴게 아닙니다. 300~400ms 안으로 나와야 에라토스테네스 체를 썼다고 볼 수 있는데, O(n^3/2)로 구하셔서 그런 것으로 보입니다.

간단하게 말씀드리자면, 소수 구하는 알고리즘을 제대로 이해하지 못하셨고, 비슷하게 짜려고 하신거 같습니다만 시간이 오버될 수 밖에 없는 구조로 짜셨습니다.

문제

문제

출처

ICPC

4948번 시간초과 문제

free0122 1년 전 0

movegreen 1년 전 1

free0122 1년 전 0

movegreen님

답변해 주셔서 감사합니다!

이번 기회에 다시 공부를 해보겠습니다!

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말