BOJ 4673 - 셀프 넘버

문제

BOJ 4673 - 셀프 넘버

d(n) = n + n의 각 자릿수의 합으로 정의한다. d에 의해 생성되지 않는 수를 셀프 넘버라 한다. 10,000 이하의 셀프 넘버를 모두 출력하라.

입력

없음 (입력 없이 10,000 이하의 셀프 넘버를 출력)

출력

한 줄에 하나씩 셀프 넘버를 오름차순으로 출력한다.

예제

풀이

에라토스테네스의 체와 유사한 방식으로, 생성자가 있는 수를 마킹하고 마킹되지 않은 수를 출력한다.

1. 크기 10001의 boolean 배열을 준비한다
2. 1부터 10000까지 각 수 i에 대해 d(i)를 계산하고, d(i)가 10000 이하이면 해당 인덱스를 true로 마킹한다
3. 1부터 10000까지 순회하며 false인 수(생성되지 않은 수 = 셀프 넘버)를 출력한다

핵심 아이디어: 모든 수에 대해 d 함수를 적용하여 "생성된 수"를 마킹하면, 마킹되지 않은 수가 셀프 넘버이다. BOJ 2231(분해합)의 역문제와 유사한 접근이다.

코드

package com.ssafy.an.day049;
 
public class Day36BOJ4673셀프넘버함수만들기 { // 4673 셀프 넘버
	public static void main(String[] args) {
		boolean[] d = new boolean[10001];
		for (int i = 1; i <= 10000; i++)
			if (d(i) < 10001)
				d[d(i)] = true;
		for (int i = 1; i <= 10000; i++) 
			if (!d[i])
				System.out.println(i);
	}
 
	private static int d(int n) {
		int sum = n;
		while (n != 0) {
			sum += (n % 10);
			n /= 10;
		}
		return sum;
	}
}

복잡도

• 시간: O(N * log N) — N개의 수 각각에 대해 자릿수 분해 O(log N)
• 공간: O(N) — boolean 배열 (N = 10,000)