BOJ 4673번 : 셀프 넘버

안녕하세요. 지난 포스팅의 BOJ 4344번 : 평균은 넘겠지에서는 1차원 배열을 기반으로 문제를 풀어보았습니다. 오늘은 백준 단계별 문제 풀이에서 함수 카테고리로 오게 되었지만 함수를 사용하지 않고 그냥 반복문, 조건문, 1차원 배열과 같은 기본적인 개념들을 위주로 문제를 풀어보도록 하겠습니다. 

 

 

완벽한 코딩은 존재하지 않습니다. 제가 제출한 코드 역시 마찬가지고 그저 참고만 해주시길 바랍니다. 

핵심 포인트

• 1차원 배열 : 리스트 자료형
• 조건문
• 반복문

 

제출 코드

self_numbers = [1] * 10000
for number in range(1, 10000) :
  if self_numbers[number] == 0 : continue
  sequence = number
  while True :
    while number != 0 :
      sequence += number % 10
      number //= 10
    if sequence >= 10000 : break
    else :
      number = sequence
      self_numbers[number] = 0

for idx in range(len(self_numbers)) :
  if self_numbers[idx] == 1 and idx > 0: print(idx)

 

설명

이와 같이 수학과 관련된 구현문제를 저희는 이미 BOJ 1110번 : 더하기 사이클이라는 문제에서 한번 보았습니다. 이와 같은 문제의 핵심은 규칙을 정확하게 이해하고 간단한 예시에 적용해보는 것 입니다. 예를 들어, 1 이라는 숫자의 카프리카 수열을 구한다고 가정해보겠습니다. 그럴려면 함수 $d(n)$이 어떤 역할을 하는 지 이해해야겠죠. 정의에 따르면 입력 숫자 $n$에 $n$의 각 자리 수를 모두 더한 수가 됩니다. 따라서, $d(1) = 1 + 1 = 2$가 되겠죠. 이를 반복해보겠습니다. 

 

$$\begin{align*} &d(1) = 1 + 1 = 2 \\ &d(d(1)) = d(2) = 2 + 2 = 4 \\ &d(d(d(1))) = d(4) = 4 + 4 = 8 \\ &d(d(d(d(1)))) = d(8) = 8 + 8 = 16 \\ &d(d(d(d(d(1))))) = d(16) = 16 + 1 + 6 = 23 \end{align*}$$

 

따라서, $1 \rightarrow 2 \rightarrow 4 \rightarrow 8 \rightarrow 16 \rightarrow 23 \rightarrow \cdots$의 수열을 얻게 됩니다. 여기서 $n \rightarrow d(n)$라는 것은 $n$이 $d(n)$의 생성자라는 것을 의미합니다. 그러므로 $2, 4, 8, 16, 23, \dots$와 같은 숫자는 셀프넘버가 될 수 없습니다. 유일하게 1만 가능하죠. 

 

여기서 저희는 아이디어를 생각해야합니다. 1부터 10,000까지 순회하면서 각 숫자로 만들어지는 모든 카프리카 수열을 저장한 뒤 나중에 출력할 때는 카프리카 수열에 포함되지 않는 값들을 출력하면 됩니다. 그러므로 각 숫자로 만들어지는 카프리카 수열을 저장하기 위한 리스트 자료형 self_numbers = [1] * 10001 을 선언합니다. 이 수열은 1일 때 해당 인덱스가 셀프 넘버, 0일 때는 셀프 넘버가 아님, 즉 카프리카 수열에 포함되는 숫자임을 의미합니다. 

 

그리고 1 ~ 10,000까지 순회하면서 이미 카프리카 수열에 포함되는 숫자라면 그냥 확인해볼필요도 없이 continue 구문을 통해 다음 숫자를 확인합니다. 그리고 $n$이 입력되면 10,000보다 작은 모든 카프리카 수열들을 계산해주기 위해 while 구문을 추가하고 만약, 카프리카 수를 계산했을 때 10,000을 넘어가면 반복문을 탈출하고 넘지 않으면 self_numbers[number]의 값을 0으로 바꾸어주어 셀프 넘버가 될 수 없음을 표시합니다. 마지막으로 $d(n)$을 구현하기 위해 두번째 while 반복문을 추가하여 각 자리 숫자의 합을 합해주면 됩니다. 여기서 중요한 점은 생성되는 $d(n)$을 이용해서 새로운 카프리카 수인 $d(d(n))$을 계산해야하기 때문에 첫번째 while 문 안에서 number = sequence로 변경해줍니다. 

 

그러면 self_numbers에는 셀프 넘버인 수들은 전부 1로 표시가 되었을 테니 다음 for문을 돌면서 1이면 값을 출력해주면 됩니다. 

 

참고자료 및 그림출처

백준 코딩 문제