[백준] 2231 - 분해합 JAVA

링크

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

2231번: 분해합

 

문제

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

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

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

출력
첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.

 

접근방법

문제에서 제시한 분해합을 식으로 표현하면 다음과 같다.

 

1. 분해합 = 생성자N + N의 각 자릿수의 합

생성자 N은 그 자체로 사용할 것이므로, 생각할 것은 N의 각 자릿수의 합이다. 그래서 각 N의 자릿수를 구하고 합을 구하는 함수를 하나 구현하였다. 그리고 가독성을 위해 분해 합의 식을 함수로 구현하였다.

생성자 N에 대한 분해합 식은 완성되었다. 이제 특정 M을 만족하는 N을 찾는 방법을 구하면 된다.

 

문제에서 분해 합의 가장 작은 생성자를 구하라는 부분을 포인트로 잡고 진행했다. 분해합 M은 생성자 N에서 나오므로, N은 M보다 작을 수밖에 없다. N은 자연수 1부터 시작하므로 1부터 M사이에 분해합 M을 만족하는 N이 존재한다. 따라서 브루트 포스 알고리즘 방식을 이용하여, 1부터 M사이에서 분해합 M을 만족하는 N을 구하였다.

 

코드

import java.util.Scanner;

public class BJ_2231 {

    public static void main(String[] args) {
        BJ_2231 test = new BJ_2231();
    }

    public BJ_2231(){
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        int answer = solution(num);
        System.out.println(answer);
    }

    public int solution(int num){
        int answer = 0;

        for (int i = 1 ; i < num ; i++){
		// 요구한 분해합 M과 일치하는 생성자 N의 계산값 비교
            if (num == cal_func(i)){
                answer = i;
                break;
            }
        }

        return answer;
    }
    
	// 분해합 = N +N의 각 자릿수의 합
    private int cal_func(int num){

        int origin = num;
        int sum = cal_digit(origin);

        return origin+sum;

    }

	//자릿수의 합
    private int cal_digit(int num){
        //int digit = 1;
        int sum = 0 ;
        while(num>0){
            //end point
            if(num/10==0){
                break;
            }else{
                //자릿수가 남아있다면 digit 추가
                sum += num%10 ;
                num = (int)num/10;
                //digit++;
            }
        }
        sum += num %10;
        return sum;

    }

}