[JAVA / 자바] 백준 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부터 분해합까지 분해합을 구해 입력값과 같으면 반복문을 종료해주고 찾은 생성자를 출력해주면 된다.

만약 분해합을 찾지 못했을 경우에는 0을 출력해주면 된다.

---

JAVA 코드 풀이

- while문

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner input = new Scanner(System.in);
        int num = input.nextInt();
        int tot, len;
        boolean flag = false; // 생성자 찾음 유무 표시
        for(int i=1; i<num; i++){
            tot = i; // 분해합 과정 중 자기 자신 더하기
            len = 1;
            while(i/len > 0) { // 각 자릿수 더하기
                tot += (i/len)%10;
                len *= 10;
            }
            if(tot == num){
                System.out.println(i);
                flag = true; // 생성자 찾음
                break;
            }
        }
        if(!flag) // 생성자 못찾았을 때
            System.out.println(0);
    }
}

while문 코드 실행 결과

- if문

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner input = new Scanner(System.in);
        int num = input.nextInt();
        int tot;
        boolean flag = false; // 생성자 찾음 유무 확인
        for(int i=1; i<num; i++){
            tot = i; // 자기 자신 더하기
            tot += i%10; // 1의 자리부터 n의 자리까지 각 자릿수 더하기
            if(i/10 > 0)
                tot += (i/10)%10;
                if(i/100 > 0)
                    tot += (i/100)%10;
                    if(i/1000 > 0)
                        tot += (i/1000)%10;
                        if(i/10000 > 0)
                            tot += (i/10000)%10;
                            if(i/100000 > 0)
                                tot += (i/100000)%10;
                                if(i/1000000 > 0)
                                    tot += (i/1000000)%10;
            if(tot == num){
                System.out.println(i);
                flag = true; // 생성자 찾음
                break;
            }
        }
        if(!flag) // 생성자 찾지 못함
            System.out.println(0);
    }
}

if문 코드 실행 결과

---

후기

while문이 if문보다 코드는 간결하게 작성되지만 실행시간은 if문이 조금 더 빠르다.

그때그때 가독성이나 효율성에 따라 상황에 유리한 방법으로 코드를 작성해주면 될 것 같다.

---

문제 원본

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