[백준 4673] 셀프 넘버

글에 개요

백준 알고리즘 4673번 "셀프 넘버" 문제입니다. 에라토스테네스의 체 개념을 알면 쉽게 해결할 수 있습니다.

앞서 다루었던, 아래 참고할 글 1번에 정리한 내용을 보시면 쉽게 푸실 수 있는 문제입니다.

에라토스테네스의 체 (Sieve of Eratosthenes)를 정리한 글 내용을 꼭 보시길 추천드립니다!!!!

이 문제는 에라토스테네스의 체의 모양에서 약간만 변경하면 해결이 가능합니다.

에라토스테네스 체를 활용한 다섯 번째 문제이므로 참고할 만한 글을 통해 여러 문제를 풀어보시는 것을 추천드립니다.

이 후 이 문제를 통해 확장할 수 있는 문제가 많기 때문에 더더욱 익히셨으면 좋겠습니다. 

[백준 4673] 셀프 넘버: https://www.acmicpc.net/problem/4673

참고할 글

1. http://brenden.tistory.com/48 ([알고리즘] 에라토스테네스의 체 정리글)
2. http://brenden.tistory.com/49 ([백준 2960] 에라토스테네스의 체)
3. http://brenden.tistory.com/50 ([백준 1978] 소수 찾기)
4. http://brenden.tistory.com/51 ([백준 4948] 베르트랑 공준)
5. http://brenden.tistory.com/52 ([백준 6588] 골드바흐의 추측)

핵심 내용

1. 에라토스테네스의 체의 모양을 조금만 변경하면 풀 수 있습니다.
2. 10001까지의 모든 셀프넘버를 판단할 수 있는 isSelfNum 배열에 담아줍니다.
3. getNum()이라는 n과 n의 자릿수를 더해주는 d(n)함수를 만들어줍니다.
4. 15 line 처럼 for문을 작성해주면 됩니다.

해결 방법

1. 셀프넘버를 판별하기 위한 isSelfNum 배열을 선언해줍니다.
2. 에라토스테네스의 체의 모양처럼 이중 for문을 작성해주면됩니다.
3. 여기서 getNum()함수 값을 15 line 처럼 for문을 작성해주면 해결됩니다.

해결한 코드

백준 참고 내용

셀프 넘버 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	15392	8188	6655	54.340%

문제

셀프 넘버는 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보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 증가하는 순서로 출력한다.

예제 입력 1 

예제 출력 1 

1
3
5
7
9
20
31
42
53
64
 |
 |       <-- a lot more numbers
 |
9903
9914
9925
9927
9938
9949
9960
9971
9982
9993