[백준/BOJ] 4673번 셀프 넘버 (java)

백준 온라인 저지(BOJ) 4673번 셀프 넘버

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

4673번: 셀프 넘버

* 사용언어 : java, 자바

 

1. 문제

양의 정수 n에 대해 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의

이때 n을 d(n)의 생성자라고 함

예를 들어, d(75) = 75 + 7 + 5 = 87 이면, 75는 87의 생성자임

 

생성자가 없는 숫자를 셀프 넘버라고 하는데,

10000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 모두 출력

 

2. 풀이

문제에 괜히 무한 수열 얘기가 있어서 처음 문제 이해할 때 조금 헷갈렸습니다.

무한 수열은 이 문제 풀이에는 필요없는 얘기고,

d(n) 함수 처리 방식 그리고 생성자와 셀프 넘버의 정의만 이해하면 됩니다.

 

생성자가 없는 숫자인 셀프 넘버를 찾는 것이 이 문제의 목표입니다.

셀프 넘버 여부를 알기 위해 d(n)에서 n을 찾아보려 했지만, 방법이 잘 보이지 않습니다.

하지만 반대로 n으로 d(n)을 구하는 것은 쉽습니다.

 

그래서 아래와 같은 방식으로 풀었습니다.

1) n으로 d(n)을 찾는 함수(getDn)를 만들고, n을 1부터 10000까지 반복하면서 d(n)을 찾았습니다.

2) 크기가 10001인 배열(isNotSelfNumber)을 만들고, d(n)이 되는 숫자가 셀프 넘버가 아니라고(true) 체크하였습니다.

3) 반복을 마친 후 배열에 체크되지 않은(false) 셀프 넘버를 출력하였습니다.

 

예를 들어

n = 1 이면 d(n) = 1 + 1 = 2 이고, 이 결과로 2는 셀프 넘버가 아닙니다. (배열의 2번 index에 체크)

n = 2 이면 d(n) = 2 + 2 = 4 이고, 이 결과로 4는 셀프 넘버가 아닙니다. (배열의 4번 index에 체크)

...

n = 10000 이면 d(n) = 10000 + 1 + 0 + 0 + 0 + 0 = 10001 이고, 이 결과로 10001은 셀프 넘버가 아닙니다.

(배열 범위를 초과하여 체크 X)

이런식으로 반복한 후에 체크되지 않은 숫자(셀프 넘버)를 모두 출력해주었습니다.

 

3. 코드

public class Main {
	public static void main(String[] args) {
		boolean[] isNotSelfNumber = new boolean[10001];
		for (int i = 1; i <= 10000; ++i) {
			int dn = getDn(i);
			if (dn <= 10000) isNotSelfNumber[dn] = true;
		}

		for (int i = 1; i < isNotSelfNumber.length; ++i) {
			if (!isNotSelfNumber[i]) System.out.println(i);
		}
	}

	private static int getDn(int n) {
		int dn = n;
		while(n > 0) {
			dn += n % 10;
			n /= 10;
		}
		return dn;
	}
}

* boolean type의 기본값은 false이기 때문에 셀프 넘버가 아닌 항목을 true로 체크하고, 체크되지 않은(false) 항목을 출력했습니다.