[백준] 4673번: 셀프 넘버

셀프 넘버

 

 

해당 문제는 에라토스테네스의 체를 통해 소수(Prime Number)를 구하는 알고리즘을 응용하면 풀 수 있다.

에라토스테네스의 체의 대한 설명은 아래 GIF를 통해 어느정도 이해 할 수 있을 것이다.

출처: 위키백과: 에라토스테네스의 체

그리고 Java이긴 하지만 GitHub에도 올려놓았었다.

github.com/JoSangYeon/Algorithm/tree/master/PrimeNumber

JoSangYeon/Algorithm

에라토스테네스의 체에 대해선 나중에 자세히 설명하는 글을 쓸 예정이지만 간단하게 정리하자면 다음과 같다.

소수는 1과 자기자신만 약수를 가지는 자연수이다. 그래서 위 사진처럼 loop를 돌릴때, 1부터 특정 숫자까지(그림에선 120) 하나씩 접근해서 하나씩 접근한 숫자의 배수들을 지워나가는 것이다.

 

그럼 위 알고리즘을 응용해서 작성한 셀프넘버 출력의 코드는 다음과 같다.

def calc():
    # 0번 인덱스를 제외한 1~10000까지의 공간을 확보
    selfNum = [True for i in range(10001)]
	
    # 1부터 판단 시작
    for i in range(1,10001):
        temp = i
        for x in range(len(str(i))):
            temp += int(str(i)[x])
        if (temp > 10000):
            continue
        else:
            selfNum[temp] = False

    for i in range(1, 10000):
        if(selfNum[i] == True):
            print(i)

calc()

위 코드에서 i가 123일때를 가정해 보자.

temp = 123이 되고 String "123"에 대해서 두번째 for문이 실행된다. 그렇다면 temp는 123 + 1 + 2 + 3 = 129로 129는 셀프 넘버가 아니게 된다.

위 같은 알고리즘으로 1부터~10000까지 수행하게된다. 모두 수행한 후에 저장소에 True인 것들만 출력하면 문제 해결