코드업 1615번 셀프 넘버 (Python)

출처

코드업 1615 셀프 넘버

---

정답

import sys

def d(n):
  generate_number = n
  while (n > 0):
    generate_number += n % 10
    n //= 10
  return generate_number

a, b = map(int, sys.stdin.readline().rstrip().split())
self_numbers = [i for i in range(b + 1)]

for i in range(1, b):
  generate_result = d(i)
  if generate_result < b + 1:
    self_numbers[generate_result] = 0

sum_of_self_number = 0
for i in range(a, b + 1):
  if self_numbers[i] > 0:
    sum_of_self_number += self_numbers[i]

print(sum_of_self_number)

---

문제

---

입출력

---

풀이

0. 전략

제너레이터의 정의

1) 제너레이터 d의 입력값은 자연수 이므로, 제너레이터로 만들 수 있는 가장 작은 숫자는 2이다 
> d(1) = 1 + 1 = 2 

2) 셀프 넘버 : 제너레이터로 생성할 수 없는 수 
예를 들어 
> 제너레이터로 만들 수 있는 가장 작은 숫자는 2 이므로 1은 셀프 넘버이다
> 제너레이터로 만들 수 있는 두 번째로 작은 숫자는 4 이므로 3은 셀프 넘버이다 
> d(2) = 2 + 2 = 4 

3) 특정 숫자 N 이 셀프 넘버인지를 알고 싶다면 d(1) ~ d(N-1) 까지 제너레이터를 호출해야 한다 
> d(N) != K 성립 여부를 알아보려면 d(1) ~ d(N-1) 까지 제너레이터를 호출해서 K가 생성되지 않음을 확인해야 함 
> 11이 셀프넘버인지 확인하기 위해 d(1) ~ d(10)까지 호출한다면 다음과 같다 
> d(1) = 1 + 1 = 2 
> d(2) = 2 + 2 = 4 
> d(3) = 3 + 3 = 6 
... 
> d(9) = 9 + 9 = 18
> d(10) = 1 + 0 + 10 = 11  즉, 10은 11의 제너레이터 이다 (11은 셀프 넘버가 아님) 


4) 입력값은 a <= b 관계이므로 셀프 넘버 판단을 위해서는 d(1) ~ d(b-1)까지 제너레이션을 호출해야 한다 

 

구현전략

1) 주어진 범위 (a ~ b) 내의 모든 수가 셀프 넘버인 것으로 가정하고 초기 배열을 생성한다 (self_numbers)
2) 주어진 범위 (a ~ b) 내의 수를 생성할 수 있는 제너레이터가 있는 지 확인한다 
   - d(1) ~ d(b-1) 제너레이터 호출 
   - d(1) ~ d(b-1) 제너레이터로 생성된 수 즉, 셀프 넘버가 아닌 수가
   - 주어진 범위 (a ~ b) 에 포함되는 경우 해당 수를 index로 가지는 self_numbers의 값을 0으로 변경한다 
   ※ d(K) 는 항상 K 보다 크기 때문에 d(b) 는 호출할 필요가 없다 
3) 주어진 범위 (a ~ b) 내의 셀프 넘버를 더한 후 출력한다 
   - self_numbers 에서 셀프 넘버가 아닌 수를 제외하고 모두 더 한다 
   - 더한 값을 출력한다 

1. 문제/입력값에 의한 초기 설정

# 문제 정의에 의해 작성한 제너레이터 d 
# 각 자리수의 수 + n 
# ex) d(123) = 1 + 2 + 3 + 123 = 129
def d(n):
  # n 을 더한다 
  generate_number = n # generate_number = 123 
  # n이 0 보다 크다면 
  while (n > 0):
    # n의 1의 자리수를 더한다 
    generate_number += n % 10 # 123 + 3 + 2 + 1 = 129
    # n을 10으로 나누어 자리수를 오른쪽으로 한 칸 옮긴다    
    n //= 10 # n = 123 -> 12 -> 1 
  return generate_number # 129 

# 셀프 넘버 여부를 판단할 범위 a, b 입력 
a, b = map(int, sys.stdin.readline().rstrip().split())
# 셀프 넘버 여부를 판단할 1차원 배열 생성 
# 각 index와 동일한 값으로 초기화한다 
self_numbers = [i for i in range(b + 1)]

2. 셀프 넘버 확인 알고리즘

# d(1) ~ d(b-1) 로 생성 가능한 수 확인 
for i in range(1, b):
  # d(i) 생성 
  generate_result = d(i)
  # d(i) 값이 확인하고자할 범위 내에 속한다면 
  if generate_result <= b:
    # self_numbers index 를 0로 표시 
    # 즉, generated_result 에 해당하는 수는 셀프 넘버가 아니므로 0으로 초기화한다 
    self_numbers[generate_result] = 0

# 셀프 넘버의 합
sum_of_self_number = 0
# 셀프 넘버 여부를 판단할 범위 a ~ b 에 대해서 
for i in range(a, b + 1):
  # 만약 셀프 넘버라면 
  if self_numbers[i] > 0:
    # 셀프 넘버를 더한다 
    sum_of_self_number += self_numbers[i]

3. 정답 출력

# 두 수사이의 셀프넘버들의 합을 출력한다.
print(sum_of_self_number)

---

반복 회차별 제너레이터 플래그 상태 변화

1) 1, 10

회차	제너레이터	제너레이터 플래그 상태 변화
1회	d(1) = 2	[0, 1, 0, 3, 4, 5, 6, 7, 8, 9, 10]
2회	d(2) = 4	[0, 1, 0, 3, 0, 5, 6, 7, 8, 9, 10]
3회	d(3) = 6	[0, 1, 0, 3, 0, 5, 0, 7, 8, 9, 10]
4회	d(4) = 8	[0, 1, 0, 3, 0, 5, 0, 7, 0, 9, 10]
5회	d(5) = 10	[0, 1, 0, 3, 0, 5, 0, 7, 0, 9, 0]
6회	d(6) = 12	[0, 1, 0, 3, 0, 5, 0, 7, 0, 9, 0]
7회	d(7) = 14	[0, 1, 0, 3, 0, 5, 0, 7, 0, 9, 0]
8회	d(8) = 16	[0, 1, 0, 3, 0, 5, 0, 7, 0, 9, 0]
9회	d(9) = 18	[0, 1, 0, 3, 0, 5, 0, 7, 0, 9, 0]
10회	d(10) = 11	[0, 1, 0, 3, 0, 5, 0, 7, 0, 9, 0]

셀프 넘버의 합 = 1 ~ 10 사이의 셀프 넘버의 합 = 1 + 3 + 5 + 7 + 9 = 25

2) 4, 8

회차	제너레이터	제너레이터 플래그 상태 변화
1회	d(1) = 2	[0, 1, 0, 3, 4, 5, 6, 7, 8]
2회	d(2) = 4	[0, 1, 0, 3, 0, 5, 6, 7, 8]
3회	d(3) = 6	[0, 1, 0, 3, 0, 5, 0, 7, 8]
4회	d(4) = 8	[0, 1, 0, 3, 0, 5, 0, 7, 0]
5회	d(5) = 10	[0, 1, 0, 3, 0, 5, 0, 7, 0]
6회	d(6) = 12	[0, 1, 0, 3, 0, 5, 0, 7, 0]
7회	d(7) = 14	[0, 1, 0, 3, 0, 5, 0, 7, 0]
8회	d(8) = 16	[0, 1, 0, 3, 0, 5, 0, 7, 0]

셀프 넘버의 합 = 4 ~ 8사이의 셀프 넘버의 합 = 5 + 7 = 12

---