파이썬으로 풀어보는 백준 4673번: 셀프 넘버

https://www.acmicpc.net/problem/4673

4673번: 셀프 넘버

 

내 풀이:

def d(num):
    letter=str(num)
    l=len(letter)
    sum=num
    for i in range(l):
        sum+=int(letter[i])
    return sum
 
delete=[]
for i in range(1,9974):
    delete.append(d(i))
 
for i in range(1,10001):
    if i not in delete:
        print(i)

664ms, 253B

셀프 넘버를 어떻게 구별할지 고민하다가 결국 셀프 넘버가 아닌 수들의 리스트를 만들었다. 그나마 시간을 줄여보기 위해 9973 이후에 만들어지는 셀프 넘버가 아닌 수는 10000을 넘는다는 사실을 이용해 범위를 1~9973으로 잡았다. 그러나 거의 10000개에 가까운 수를 함수에 넣어 계산해야 했으며 이후 다시 10000개의 수가 셀프 넘버인지 검토해야 했다.

 

kimpi님 풀이:

a = [True]*20000
for i in range(10):
    for j in range(10):
        for k in range(10):
            for l in range(10):
                a[1001*i+101*j+11*k+2*l] = False
for i in range(10000):
    if a[i] == True:
        print(i)

56ms, 230B

kimpi님의 코딩을 보면 1001, 101, 11, 2에 주목해야 한다. 나는 셀프 넘버를 수학적으로 구별하지 못했다.

a는 20000개의 True가 저장되있는 리스트이다. 그리고 1001*i+101*j+11*k+2*l 의 형태로 표현되는 수는 셀프 넘버가 아니라는 사실을 이용하였다.

 

함수 카테고리에 있는 문제이니만큼 함수를 정의하여 문제를 풀기 위해 노력하였지만 때문에 오히려 생각의 폭이 좁아진 것 같다.