[Baekjoon] 4673 - 셀프 넘버

📝 문제

 

 

🔑 풀이 과정

항상 문제를 풀 때 문제를 꼼꼼하게 읽고 힌트를 얻는게 중요하다고 생각하는데, 이 문제도 그렇다.

양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다.

이 부분이 큰 힌트가 됐다.

 

· 우선 풀이를 위해 boolean 배열을 선언한다.

또 문제가 10,000보다 작거나 같은 셀프넘버를 출력하라고 범위를 딱 정해줬기 때문에,

배열의 크기를 10,001로 준다.(인덱스를 10000까지 사용하기 위함)

 

하나의 숫자 n에 대해서 d(n)을 true로 바꿔줄 것이다.

그리고 1부터 10000까지 순회하면서 false인 경우(셀프 넘버)를 출력하면 되는 것이다.

 

· d() 함수를 메서드로 작성해준다.

d() 함수의 출력값을 true로 바꿔주고, 다시 d() 함수의 입력값으로 넣어서 계산하여 무한 수열을 구현해준다.

여기서 인덱스 오류가 나지 않게 출력값이 10000이 넘으면 true로 바꿔주는 부분 수행 X

 

· 그리고 d() 함수를 실행할 때, 이미 true인 경우는 실행을 하지 않게 했다.

for(int i = 1; i <= 10000; i++){
    if(arr[i])
        continue;
    else
        D(i);
}

왜냐면 무한수열 이기 때문에 이미 true라는 것은 한 번 무한수열 계산에 포함됐기 때문에 굳이 계산할 필요가 없다는 뜻

[예시]

1로 시작했을 때,

d(1) = 1 + 1 = 2
d(2) = 2 + 2 = 4
d(4) = 4 + 4 = 8
d(8) = 8 + 8 = 16
d(16) = 16 + 1 + 6 = 23
d(23) = 23 + 2 + 3 = 28
d(28) = 28 + 2 + 8 = 38
... 반복

여기서 결과값인 2, 4, 8, 16, 23...은 true로 변환된다.

그 후 1로 시작한 무한수열이 끝이 났을 때,
2로 시작하는 무한수열을 계산해야 되지만
이미 2로 시작하는 무한수열은 1의 무한수열을 계산할 때 수행됐다. (4, 8, 16 ... 또한 그렇다)

즉, 이미 true인 경우는 수열을 돌려봤자 의미가 없다.

 

 

 

🔓 답안

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;

public class Main {

    static boolean arr[];

    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        arr = new boolean[10001]; //인덱스 0부터 10000까지 사용가능

        for(int i = 1; i <= 10000; i++){
            if(arr[i]) //boolean값이 true인 경우, 이미 한 수열의 출력값이 됐고, 또 다른 수열의 입력값이 됐으므로(무한수열) pass한다.
                continue;
            else
                D(i);
        }

        for(int i = 1; i <= 10000; i++){
            if(!arr[i]) //false 일 때 셀프넘버
                sb.append(i).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();

    }

    static void D(int n){
        if(n > 10000)
            return;
        else{
            int num = n;
            int sum = n;

            while(num > 0){
                sum += num % 10;
                num = num / 10;
            }

            if(sum <= 10000){
                arr[sum] = true;
                D(sum); //무한 수열
            }
        }
    }

}

 

 

 

🖤 알고리즘 분류

- 수학

- 구현

- 브루트포스 알고리즘