글 읽기 - python 시간 초과 오류

6210seok 2년 전 0

시간 초과라고 뜹니다. 방법이 틀리진 않은 것 같은데 어떤 부분을 수정해야 속도가 빨라질까요?

def self_num(x):
    for i in range(1,x+1):
        result = -1
        for N in range(1,i):
            z = str(N)
            for j in range(len(z)):
                N += int(z[j])
            if i == N:
                result = 0
                break
        if result == -1:
            print(i)
            
self_num(10000)

lcr7324 2년 전 1

지금 코드는 i가 1000이라면 d(1)이 i인지 확인하고, d(2)가 i인지 확인하고, ..., d(999)가 i인지 확인합니다.

그 다음 i가 1001이면 또 다시 d(1)이 i인지 확인하고, d(2)가 i인지 확인하고, ..., d(1000)이 i인지 확인합니다.

달라지지 않는 d(N) 값을 이렇게 계속 반복해서 구할 필요가 있을까요?

amsminn 2년 전 1

N=10000이기 때문에 $O(N^2logN)$는 시간초과의 여지가 있습니다.

잘 생각해보면 n<=10000이기 때문에 범위에서 특정한 x가 셀프넘버라면 생성자는 구간 $[x-36,x]$에 존재합니다.

그래서 $O(36*N)$으로 해결할 수 있습니다.

아래는 정답처리를 받은 제 코드입니다.

main(){
    for(int i=1,f=1;i<=10000;i++,f=1){
        for(int j=1>i-36?1:i-36;j<=i;j++){
            if(j+j/1000+j%1000/100+j%100/10+j%10==i)f=0;
        }
        if(f)printf("%d\n",i);
    }
}

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

문제

문제

출처

ICPC

python 시간 초과 오류

6210seok 2년 전 0

lcr7324 2년 전 1

amsminn 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말