백준/2231 분해합

분해합 성공다국어

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

192 MB

106616

48833

38455

45.276%

문제

어떤 자연수 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 복사

216

예제 출력 1 복사

198

---

풀이

가장 작은 생성자를 출력해야한다.

 

예제에서 216이라는 분해합을 만드는 생성자는 198을 확인할 수 있다.

 

216이라는 분해합을 만드는 생성자는 무조건 216보다 작은 값에서 나온다. -> 생성자 + 각 자리수이므로

 

거기다가

 

가장 작은 생성자를 찾으려면

 

1 ~ 분해합 값까지 반복해서 분해합을 계산해본 후 입력된 분해합과 같은 경우 해당 생성자를 출력해주면

 

가장 작은 생성자가 출력될것이다. ( 수가 작은값부터 체크하면서 올라가니까)

 

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
import java.util.Map.Entry;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());

        for (int i = 1; i <= n; i++) {
            if (check(n, i)) {
                return;
            }
        }
        bw.write(0+"");

        bw.flush();
        bw.close();

    }

    public static boolean check(int n, int number) throws IOException{
        char[] numberChar = Integer.toString(number).toCharArray();
        int sum =number;

        for (char currentNumber : numberChar) {
            sum += Character.getNumericValue(currentNumber);
        }
        if (sum == n) {
            bw.write(number + "");
            bw.flush();
            return true;
        }
        return false;

    }
    
}

 

다른사람풀이

1. 브루트포스

자신의값 + 각 자리수값 을 일일히 구해서 비교해본다.