AlgorithmBOJ

백준 분해합 2231

, ,

1. 문제 링크

1.1. 백준 분해합 문제

2. 문제 조건

2.1. 문제

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.

자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.

2.2. 입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

2.1. 컴퓨팅적 사고

  • 분해합을 구하기 위해서는 M은 N의 생성자이여야한다. 가 가장 중요한 조건이였습니다.
    예를 들어보겠습니다.
    N이 216일 경우 (216+2+1+6) => 198이 됩니다.
    즉,198은 225의 분해합입니다.

분해합의 원리
각 자리의 수 + 분해합 M의 값 = N이 되는 경우를 찾아주면 되는 문제였습니다.
브루트포스를 사용하여 모든경우 i=1~100000까지의 값을 순회하면서 N의 값과 같은 경우를 찾아주었습니다. 정수값을 문자열로 변경하여 각 자리의 값의 합을 저장시킨후 (i의 값 + 각 자리 값의 합) 이 같을 경우 값을 찾아주었습니다.

회고
처음에 문제의 뜻을 제대로 파악못하였는데 직접 써보면서 하나씩 대입해보니까 쉽게 풀 수 있었던 문제였습니다. 약 40분정도 소요되었던 문제였습니다.

문제에서 주어진 각 분해합의 개념을 잘 파악하고 브루트포스로 값을 찾아주면 쉽게 도출 할 수 있습니다. N의 값과 같은 생성자를 모두 answer 변수에 넣어준 후 Collections.min() 함수를 사용하여 최솟값을 찾아주었습니다.

2.2. 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class 분해합 {
    static ArrayList<Integer> answer = new ArrayList<>();
    public static void main(String[] args) {
        int n = 0;
        Scanner sc= new Scanner(System.in);
        n = sc.nextInt();

        for(int i=1; i<=1000000;i++){
            String str = Integer.toString(i);
            int str_value = 0;
            for(int j=0; j<str.length(); j++) {
                str_value += Integer.parseInt(String.valueOf(str.charAt(j)));
            }
            dfs(n,i,i+str_value);
        }

        int min =0;
        if(answer.size() != 0) {
            min = Collections.min(answer);
        }
        System.out.print(min);
    }

    private static void dfs(int n, int value, int sum) {
        // sum == n의 값과 같을 경우 즉, 생성자일 경우
        if(sum == n){
            answer.add(value);
            return;
        }
    }
}


Share