[백준 4673번] 셀프 넘버(JAVA)

문제 풀러가기✍🏻

 

---

서론

난이도가 갑자기 올라가서 하루종일 못 풀다가 결국 12시 넘어서 통과를 겨우 할 수 있었다. 

개근상은 이번달도 틀린 것 같습니다.

문제

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

시행착오(Trial&Error)

클래스 이름이나 메서드 이름 관련 문제였으므로 따로 복기할 내용은 없을 것 같다.

풀이(Solution)

 33은 39의 생성자이다.

이 문장을 이해하는 것이 쉽지 않았다.

33이 생성자라는 건지 39가 생성자라는 건지... 물론 풀고 나면 어렵지 않지만, 처음에 맞닥뜨렸을 땐 뭔 말인가 싶었다.

 

생성자가 없는 숫자를 '셀프 넘버'라고 한다. 

셀프넘버를 출력하는 것이 우리가 구현해야 하는 함수의 기능이다.

 

논리

셀프넘버를 출력하는 것은 곧,

생성자를 가지고 있는 숫자들, 다시 말해 셀프넘버가 아닌 숫자들을 구별할 수 있는 조건문을 만들어서 '역' 처리(!)를 한 후 출력하면 되지 않을까 싶었다.

 

다시 생성자로 돌아와서,

33은 39의 생성자라는 문장을 보고 알 수 있는 건, 39는 생성자를 가지고 있기 때문에 셀프 넘버가 아니다.

 

초점을 33이 아니라 39에 두어야 한다.

그렇다는 건, 어떠한 조건문을 만족하면 39가 출력되면 된다.(역 처리 문제는 나중으로 미룬다. 우선 문제를 작게 쪼개자)

 

어떠한 조건문이란 생성자의 조건을 뜻하는데, 문제를 살펴보면 

33 + 3 + 3 = 39

33 + 3 + 3 = 39

이게 생성자를 나타내는 식이다.

33이 39의 생성자라고 했으니까 

33에 각 자리 수 십의 자리 3과 일의 자리 3을 더하면 39가 된다. 따라서, 33은 39의 생성자이다.

잊지 말아야 할 사실은 39는 셀프 넘버가 아니다.

문제에서 조건을 10000 이하의 수로 제시했기 때문에, 일의 자리부터 만의 자리 까지 변수로 처리했다.

int sum = 0;  // 각 자리수의 합을 저장할 변수 선언
int a, b, c, d, e;  // 만의 자리, 천의 자리, 백의 자리, 십의 자리, 일의 자리 1은 2의 생성자
int i = 1;
while(i <= 10000) {
    int cnt = 0;
    int j = 1;
    while(j <= 10000) {
        a = j / 10000  % 10;
        b = j / 1000 % 10;
        c = j / 100 % 10;
        d = j / 10 % 10;
        e = j % 10;
        sum = a + b + c + d + e;

while문을 이중으로 작성했다.

두 while문의 조건 중, '셀프 넘버'인지 아닌지 판별하고자 하는 변수는 'i'이다. 이걸 확실히 하지 않으면 조건문을 작성할 때 햇갈린다.

이제 각 자리 수의 합을 구하는 로직을 작성했으니, 조건문을 작성해보자.

if(sum + j == i) {
    cnt++;
}

조건문 뜻 : j가 i의 생성자라면

조건문이 참일 경우 내용 : 카운트를 뜻하는 변수 cnt에 1을 증가시킨다. 

 

문제에서 생성자가 두 개 이상일 수 있다고 제시했기 때문에, break문을 넣을 필요가 없다고 판단했다.

생성자가 한 개보다 많은 경우도 있다. 예를 들어, 101은 생성자가 2개(91과 100) 있다. 

    j++;
}
if(cnt == 0) {
    System.out.println(i);
}

j++을 통해 다음 반복문을 실행시킬 수 있도록 한다.

 

조건문 cnt == 0 의미 : 변수 i에 대해 생성자가 하나도 존재하지 않는다면, 즉 '셀프 넘버'라면! i를 출력한다

 

코드

class Main {
    public static void main(String[] args) {
        int n = 1;
        int sum = 0;  // 각 자리수의 합을 저장할 변수 선언
        int a, b, c, d, e;  // 만의 자리, 천의 자리, 백의 자리, 십의 자리, 일의 자리 1은 2의 생성자
        int i = 1;
        while(i <= 10000) {
            int cnt = 0;
            int j = 1;
            while(j <= 10000) {
                a = j / 10000  % 10;
                b = j / 1000 % 10;
                c = j / 100 % 10;
                d = j / 10 % 10;
                e = j % 10;
                sum = a + b + c + d + e;
                if(sum + j == i) {
                    cnt++;
                }
                j++;
            }
            if(cnt == 0) {
                System.out.println(i);
            }
            i++;
        }
    }
}