백준 / 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을 출력한다.

[예제 입력]

216

[예제 출력]

198

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(); 
        int result = 0; 

        for (int i = 0; i < n; i++) {
            int sum = 0;
            sum += i;

            int num = i;
            while(num>0) {
                sum += num%10;
                num/=10;
            }

            if(sum == n) {
                result = i;
                break;
            }
        }
        System.out.println(result);
    }
}

 

답을 result란 변수로 설정했고

각 자릿수와 result값을 더한 값을 sum이라고 두었다.

 

result와 result의 각 자릿수를 합한 값이 문제에서 주어진 수 n과 같으면

그 값이 생성자이다.

 

for문을 돌며 n보다 작은 값 중 어떤 값이 n의 생성자인지 구했다.

주의할 점은, 생성자가 여러 개 일 수 있는데, 가장 작은 생성자를 구해야 하므로 break문을 추가해줘야 한다.

break문을 추가하지 않으면, 가장 큰 생성자가 저장될 것이다.

 

---

브루트포스 알고리즘 사용! 

(1부터 입력받은 정수 n까지 한 개씩 모두 탐색)

탐색 도중 생성자 찾으면 종료하고 해당 생성자 출력하고, n 넘길 때 까지 생성자 찾지 못 하면 0 출력

 

다른 사람들 풀이를 찾아보니, 거의 내가 짠 코드대로 짰다.

여기서 좀 더 응용한 방법이 있었는데,

시간을 단축하기 위해 탐색해야 하는 범위를 줄여주는 방법이었다. ( * 참고 : https://st-lab.tistory.com/98)

 

정수 n이 주어졌을 때, 해당 수 n은 k와 k의 각 자릿수 합이다.

예로, 네자릿수 정수 n이 들어오면 해당 n을 만드는생성자는? 임의의 k와 k의 각 자릿수!

 

n(4) = k + k1 + k2 + k3 + k4

이항하면?

n(4) - k1 - k2 - k3 - k4 = k

 

즉, 네자릿수 n의 각 자릿수 합이 최대인 경우는?

9+9+9+9일 것!

 

따라서, 입력받은 n에 대해 자릿수의 길이만큼 9를 빼주면 된다. (세자릿수면 9를 3번, 네자릿수면 4번 ..)

 

결론적으로, n-(9*n의 길이만큼)부터 n까지 탐색하면 된다!

for(int i=0; i<n; i++)

위의 코드를 아래처럼 바꿔주면 된다.

for(int i=(n-(9*n.length)); i<n; i++)