[백준 #4673번 JAVA] 셀프 넘버 풀이

 

📄 셀프 넘버 [백준 4673번]

🔗 [전체 소스 코드]
🔗 [문제 풀러 가기]

---

문제 해설

문제는 에라토스테네스의 체의 개념을 활용하여 문제를 해결하였습니다. 먼저 문제의 조건을 살펴보며 해결방법을 알아보겠습니다.

문제 조건

1. d(n) = n + n의 각 자리수
2. n은 d(n)의 생성자라고 한다.
3. n을 시작으로 d(n), d(d(n)), ... 과 같은 무한 수열을 만들 수 있다.
4. 생성자가 없는 수는 셀프 넘버라고 한다.
5. 10000이하의 모든 셀프 넘버를 찾아라.

문제를 풀기 위해선 d(n)을 이해해야 합니다. d(n)은 문제에서 제시된 것과 같이 d(n) = n + n의 각 자리수 입니다. 그렇다면 여기서 생각해봐야 할 점은 n으로 인해 d(n)이 만들어 집니다. 또한 d(n)은 n보다 무조건 커지게 됩니다. 이 점을 활용한다면 쉽게 문제에 접근할 수 있습니다. 왜냐하면 d(n)은 자신보다 작은 수로 만들어지기 때문에 n이 자신보다 작은수로 만들 수 있는 모든 d(n)안에 속하지 않는다면 셀프넘버이기 때문입니다.

즉, 1부터 10000까지 만들 수 있는 모든 d(n)을 찾았을 때 만들어지지 않는 수는 모두 셀프 넘버가 됩니다. 이는 에라토스테네스의 체의 개념과 비슷하게 구현할 수 있으며 예제를 보면 쉽게 이해하실 수 있습니다.

• 에라토스테네스의 체의 개념을 모르신다면 위키피디아 - 에라토스테네스의 체를 확인하시기 바랍니다.

예제 1

Q : 20 이하의 셀프넘버를 찾아라.

A : 1, 3, 5, 7, 9, 20

먼저 1부터 20까지의 숫자를 확인할 수 있는 표를 만들면 아래와 같습니다. 만약 이 표가 채워진다면 해당 숫자를 만들 수 있는 생성자가 존재한다는 의미이므로 셀프넘버가 될 수 없습니다.

n = 1일 때 만들어 질 수 있는 d(n) 상태

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
d(n)		o		o				o								o

n = 1일 때 16까지 d(n)을 만들 수 있습니다. 다음으로 n = 2일 때 만들 수 있는 모든 d(n)을 확인 합니다. 이 때 2는 자신보다 작은 수(n = 1)일 때 만들 수 있는 d(n)에 속하므로 셀프넘버가 될 수 없습니다.

n = 2일 때 만들어 질 수 있는 d(n) 상태

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
d(n)		o		o				o								o

n = 1일 때 이미 n = 2일 때 만들 수 있는 d(n)을 모두 구했기 때문에 d(n)의 상태는 같습니다.

n = 3일 때 만들어 질 수 있는 d(n) 상태

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
d(n)		o		o		o		o				o			o	o

3의 경우 n이 3이하일 때 만들어질 수 있는 d(n)에 속하지 않으므로 셀프넘버 입니다. 이렇게 1부터 20까지 만들 수 있는 모든 d(n)을 구해나가며 셀프넘버를 구합니다.

n = 4일 때 만들어 질 수 있는 d(n) 상태

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
d(n)		o		o		o		o				o			o	o

n = 5일 때 만들어 질 수 있는 d(n) 상태

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
d(n)		o		o		o		o		o	o	o	o		o	o	o

.
.
.

n = 20일 때 만들어 질 수 있는 d(n) 상태

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
d(n)		o		o		o		o		o	o	o	o	o	o	o	o	o	o

글보단 코드를 보면 더 이해하기 쉽습니다.

---

🌱 main 함수

// 전역 변수
private static boolean[] selfNumber;
private static final int MAX_NUM = 10000;

public static void main(String[] args) throws IOException {
    selfNumber = new boolean[MAX_NUM + 1];
    solve();
}

🌱 solve 함수

셀프넘버를 찾는 함수입니다.

private static void solve() {
    for (int i = 1; i <= MAX_NUM ; i++) {
        if (!selfNumber[i]) System.out.println(i);

        findNonSelfNumber(i);
    }
}

🌱 findNonSelfNumber 함수

n으로부터 구할 수 있는 모든 d(n)을 구하는 재귀 함수입니다.

private static void findNonSelfNumber(int number) {

    int constructorNumber = number;
    int dn = constructorNumber;

    while(constructorNumber > 0) {
        dn += constructorNumber % 10;
        constructorNumber /= 10;
    }

    if (dn > MAX_NUM || selfNumber[dn]) return;

    selfNumber[dn] = true;
    findNonSelfNumber(dn);
}

---

💡 Github에 더 많은 문제 풀이가 있습니다.

Programmers 문제 풀이

BaekJoon Online Judge 문제 풀이