알고리즘

[파이썬] 단계별 백준 문제 풀기 - 4673 함수 (셀프넘버)

햄❤️ 2021. 3. 6. 19:26
반응형

Hint : 전체 수에서 생성자가 있는 수를 구해서 빼주자!!!

 

문제

셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다.

양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다. 

예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다음 수는 39 + 3 + 9 = 51, 다음 수는 51 + 5 + 1 = 57이다. 이런식으로 다음과 같은 수열을 만들 수 있다.

33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ...

n을 d(n)의 생성자라고 한다. 위의 수열에서 33은 39의 생성자이고, 39는 51의 생성자, 51은 57의 생성자이다. 생성자가 한 개보다 많은 경우도 있다. 예를 들어, 101은 생성자가 2개(91과 100) 있다. 

생성자가 없는 숫자를 셀프 넘버라고 한다. 100보다 작은 셀프 넘버는 총 13개가 있다. 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97

10000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하시오.

입력

입력은 없다.

출력

10,000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 증가하는 순서로 출력한다.

 

<<코드>>

all_nums = set(range(1,10001))
non_self = set() #빈 집합으로 만들어준다

for n in range(1,10001):
  for i in str(n): #n이 33일때
    n += int(i) #n은 33 + 3(int(1)) + 3(int(2)) = 39
  non_self.add(n) #non_self 집합에 추가 #집합 값 추가 함수 add() 사용
  
#생성자가 있는 값을 구해서 전체에서 빼주면 = 셀프넘버 집합  
self_nums = sorted(all_nums-non_self) #집합은 순서대로 나열되지 않지만, 문제는 순서대로 출력되길 원함 sorted() 함수로 정렬
for x in self_nums: #그대로 for문으로 출력
  print(x)

 

<<결과값>> 아래 숫자 더 있음

1
3
5
7
9
20
31
42
53
64
75
86
97
108
110
121
132
143
154
165
176

셀프넘버는 문제를 이해하기 힘들었다. 생성자가 없는 값을 어떻게 구해야할까 생각하다가 생성자가 있는 값을 전체에서 빼주기로 했다.

그래서 전체 집합을 만들고, 생성자 집합을 만들어서 시작했다.

 

 - 집합은 순서대로 나오지 않으므로 sorted() 함수를 써서 순서대로 맞췄다.

 - 함수를 썼어도 됬을텐데, 코드가 더 길어지는 느낌이라 집합과 for문만 이용했다.

 - 집합 함수인 add()로 생성자가 있는 값들을 non_self() 함수에 추가했다.

728x90
반응형