[알고리즘] 백준 4673 셀프넘버

문제링크

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

문제 설명

• 양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다.
• d(n) = sum(n의 각 자릿수) = m 이며
• n의 생성자는 m 일 때, 1 부터 10000까지 생성자가 없는 숫자를 출력하라.

주제

• 함수

난이도

• 하

풀이

self_number = [True] * 10000
self_number[0] = False      # 1로 시작하는 숫자와 인덱스를 동일하게 맞추기 위해서 0번째 인덱스는 None으로 처리한다.

for num in range(1, 10000):
    total = num + sum(map(int, str(num)))   # 숫자를 string형으로 변환하여 map을 통해 한 자릿수씩 쪼갠 후 int형으로 다시 바꿔 sum을 구한다.
    if total < 10000:
        self_number[total] = False          # 생성자로 출력된 결과는 False

for i in range(len(self_number)):
    if self_number[i]:          # True 만 반환해준다.
        print(i)

풀이 방법

• 1. 셀프 넘버를 True라고 할 때,
• 2. 10000개의 True 배열을 임의로 생성한다. (10000 까지의 값을 출력해야함으로)
• 3. 1부터 10000까지 모든 수를 루프를 돌려 d(n)으로 계산한다.
• 4. 3에서 d(n)으로 통해 출력된 결과는 셀프넘버가 아니므로 2에서 생성한 배열에서
     해당 인덱스는 False로 전환한다.
• 5. 3과 4의 반복작업이 끝나면 최종적으로 True로 남아있는 배열의 인덱스를 출력한다. (인덱스값 = 셀프넘버)

풀이하면서 고민했던 점

• 백준에서는 마지막 출력값이 9993인데 내 코드에서는 계속 9999번까지 출력이 되었다.
  왜 그럴까하고 한참을 고민하던 중 아래 for문에서 조건이 문제였다는 것을 발견했다.

내가 원하는 값은 10000이하의 total 값이지만 아래 for문에서는 10000을 넘을 수 밖에 없는 구조로 되어있다.

 * 초기 코드

for num in range(1, 10000):
    total = num + sum(map(int, str(num)))   
    self_number[total] = False # if문 없음

아래와 같이 3번째 줄에 if문을 추가하니 total이 10000까지 일때만 진행되어 원하는 출력 값을 얻을 수 있었다.

 * 수정 코드 (3번째 줄에 if문이 추가됌)

for num in range(1, 10000):
    total = num + sum(map(int, str(num)))  
   if total < 10000:		#if 문 추가
   	self_number[total] = False 

문제를 풀고 알게된 개념 및 소감

• 이번 문제는 며칠전에 처음보고 어렵다고 생각해서 스킵했다가 다시 풀게 된 문제인데, 여전히 어려웠지만 그래도 이번에는 크게 막히는 거 없이 전체적인 틀을 잡을 수 있었다. 문제는 저 if문 하나를 알기까지 세시간정도 걸려서 결과적으론 이 한 문제 푸는데 다섯시간을 쓴거 같다.
  하.. 난이도 하 문제인데 나중에 중으로 가면 얼마나 고생하려고ㅠㅠㅠ
  하지만 이번 문제만큼은 다른 문제들에 비해 인터넷 도움도 덜 받으면서 풀었으니 이것또한 공부라고 생각하고!
  이제 다음 문제 풀러 가야겠다 슝슝~~