[Java] 백준(브론즈-2) 2231번 - 분해합

문제 풀이

---

이 문제는 완전탐색 알고리즘을 활용하여 N의 생성자가 되는 모든 경우를 탐색해야 한다.
N까지의 수들 중에서 [자기 자신 + 자기 자신의 각 자리수의 합] 이 N이 되는 수를 찾으면 된다.

아이디어 도출

• N의 범위는 1부터 1,000,000 이기에 1부터 N까지 순회하며 분해합을 통해 N을 만들 수 있는 수를 찾는다.
• N의 생성자를 찾았다면 N의 생성자를 변수에 저장한 후 반복문을 탈출한다.

위 아이디어를 토대로 코드를 작성해보자.

int N = Integer.parseInt(br.readLine());
int constructor = 0;

먼저 N을 입력받고, 반복문 내에서 찾은 생성자 값을 담을 constructor를 0으로 초기화 해주자.
constructor를 0으로 초기화하는 이유는 혹시나 N의 생성자가 없다면 0을 반환해야 하기 때문이다.

for(int i=1; i<=N; i++) {
    int sum = i + calSum(i);
    if(sum == N) {
        constructor = i;
        break;
    }
}
bw.write(constructor+"\n");

다음으로 1부터 N까지 반복문을 돌면서 N의 생성자가 되는 수를 찾는다.
‘자기 자신(i) + 자기 자신(i)의 각 자리수의 합’이 N이라면 i는 N의 가장 작은 생성자이기에 앞서 초기화했던 constructor에 i를 담아주고 반복문을 종료하면 된다.

public static int calSum(int x) {
    int sum = 0;
    int n = x;
    while(n>0) {
        sum += n%10;
        n /= 10;
    }
    return sum;
}

위에서 사용했던 calSum 함수의 내용을 간단히 보자면, while문에서 매개변수로 받은 수를 10으로 나눠가며 각 자리수를 구하고 각 자리수의 합을 sum에 담아 반환한다.

작성코드

import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        
        int constructor = 0;
        for(int i=1; i<=N; i++) {
            int sum = i + calSum(i);
            if(sum == N) {
                constructor = i;
                break;
            }
        }

        bw.write(constructor+"\n");
        bw.flush();
        bw.close();
        br.close();
    }   

    public static int calSum(int x) {
        int sum = 0;
        int n = x;
        while(n>0) {
            sum += n%10;
            n /= 10;
        }
        return sum;
    }
}

회고

• 주어진 N의 범위에 비해 간단한 아이디어로 쉽게 접근하여 풀 수 있었던 문제였다.