[BOJ] 백준 2231 분해합

출처: https://www.acmicpc.net/problem/2231

Approach

완전탐색 유형 문제이다.

완전탐색 기법이란?

자연수 N이 주어졌을 때, 가장 작은 생성자를 구해야 한다.

  → X가 생성자 일 때, X + (X의 요소들 각각을 더한 수) = N

      ex) 156 + 1 + 5 + 6 = 168 (=N)

 

수학적 특성을 찾아내서 탐색 범위를 줄일 수도 있겠지만

N의 범위가 크지 않기 때문에 1 ~ N 까지 모든 Case를 시도해보면 된다.

생성자 X의 구성하는 숫자를 하나씩 더하기 위해서 mod 연산자(%) 이용

---

#include <iostream>

using namespace std;

int main()
{
    // freopen("input.txt", "r", stdin);
    int N, total, digit;
    cin >> N;
    for (int i = 1; i < N; ++i)
    {
        total = i; // 자기자신
        
        digit = i;
        while (digit)
        {
            // 각 구성
            total += digit % 10;
            digit /= 10;
        }

        if (total == N)
        {
            cout << i << endl;
            return 0;
        }
    }

    cout << "0" << endl;
}

 

Java

import java.util.Scanner;

public class Main {    
    public static void main(String[] args) {
        Scanner sc = new  Scanner(System.in);
        
        int N = Integer.parseInt(sc.next());
        
        int idx = 1;
        
        while(true) {
            
            // 각 자리의 수의 합들을 구한다.
            int sum = sum_of_digits(idx);
            
            // 각 자리의 수의 합과 원래 숫자와 합한다.
            sum += idx;
            // 해당 결과가 N이면 N의 생성자로 출력하고 종료
            if(sum == N) {
                System.out.println(idx);
                return;
            }
            // 더 이상 분해합을 해도 만족하지 못할 거 같으면 종료
            if(idx >= N) {
                break;
            }
            idx++;
        }
        
        // 생성자를 찾는 것에 실패 했다면 '0'을 출력
        System.out.println("0");
        
    }


    private static int sum_of_digits(int num) {
        
        int sum = 0;
        
        // num이 1의 자리의 수가 될 때까지 반복한다.
        while(num / 10 != 0) {
            // 현재 num의 1의 자리수를 sum에 더해준다.
            sum += num % 10;
            
            // 자릿수를 줄인다.
            num = num / 10;
        }
        
        // 반복문 후 남은 한 자리수를 sum에 더한 후 반환한다.
        sum += num;
        
        return sum;
    }
}