백준 | 4673번 셀프넘버, 파이썬

 

입력은 없고 출력만 있는 문제이다.

정리하면 숫자고 ​

입력은 없고 출력만 있는 문제.

정리하자면, 숫자가 주어지고, 그 숫자와 그 숫자의 각 자리수들을 합하는걸 반복하면 무한 수열을 만들 수 있는데,

이 때, 만들기 전의 숫자가 생성자이다.

이 생성자가 없는 숫자들이 있는데, 이 숫자들을 찾아서 10000이하까지 출력하는 문제

일단 한번 문제를 생각 해 봤다.

​

결론은 생성자가 없는 숫자를 찾는건데,

​

1부터 시작하는 수열의 다음숫자부터는 전부 생성자가 있는거고 1은 없는거고

2는 1 +1 로 만들어져서 제외가되고,

마찬가지로 3부터 시작하는 수열의 다음 숫자부터 전부 생성자가 있는거니까

싹 다 제외시키고 반복문을 돌리면 될거라고 생각했다.

 

내 생각을 글로 하나씩 정리 해 보았다.

 

#생각1. 크기 10000인 리스트를 만들고 전부 0으로 초기화한다.

#생각2. 1부터 시작해서 1을 제외하고 1로 만들어지는 수열을 10000까지 반복한다.

           이제 만들어진 수열들은 1을 제외하면 전부 다 생성자가 있다.

#생각3. 그렇기에 1을 제외한 수열의 값들을 인덱스로 하며 리스트에 +1을 한다.

#생각4. 반복문을 통해서 1부터 10000까지 돌리는데, 만약 그 리스트의 값이 0이 아니라면,

           그 수는 수열을 만들 필요가 없다.

#생각5. 리스트에서 0인값들만 출력한다.

 

위처럼 생각하고 코드를 써 내려 갔다.

 

 

def self_number(n): #그 수를 시작으로 해서 수열의 다음을 만들어주는 함수
    result = n
    while True:
        num = n % 10
        result = result + num
        n = int(n / 10)
        if n == 0:
            break
    return result
lst = [0 for i in range(10001)]#인덱스 헷갈리지 않으려고 그냥 0은 제외하고 1부터 10000까지 만듦
lst[0] = 1
for i in range(0,10001):
    if lst[i] != 0:
        i = i + 1
    elif lst[i] == 0:
        j = i
        while True:
            j = self_number(j)
            if j > 10000:
                break
            lst[j] = lst[j] + 1

for k in range(0,10001):
    if lst[k] == 0:
        print(k)

 

 

결과는 잘 나오고 채점하면 맞다고 나왔다.

 

늘 드는 생각인데, 인덱스를 여러 개를 사용하면 헷갈려서 코드 쓸때 막히곤 한다.

 

문제 출처

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