[백준 2231번] 분해합 문제 - Java

 

완전 탐색 알고리즘)

문제에서 정의된 N의 생성자 M들 중에서 가장 작은 생성자를 구해내는 프로그램을 작성하라고 제시하였습니다.

따라서 1부터 하나씩 분해합을 구하고, 생성자가 맞는지 확인하도록 코드를 작성하고자 했습니다.

 

첫 번째 시도)

M을 1부터 시작해서 분해합을 구한 다음에 N과 비교하게 됩니다.

만약 분해합이 N과 동일하면 해당 값을 result 변수에 저장하고 반복문을 탈출하는 반면, 동일하지 않으면 코드를 반복 수행하게 됩니다. 

 

import java.util.Scanner;

public class decompose_2231 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();   	// 자연수
        int result = 0;

        for(int M = 1; M < N; M++) {
            int div = M;
            int decompose = 0;      // 분해합

            // M의 각 자리수를 더함
            while(div > 0) {
                decompose += (div % 10);
                div /= 10;
            }

           // 분해합이 N과 동일하면 생성자이므로 저장
           if(decompose + M == N) {
                result = M;
                break;
            }
        }
        System.out.println(result);
    }
}

 

위의 코드는 정상적으로 동작했습니다.

 

코드를 제출하고 탐색하는 과정을 더 줄일 수 있는 방법이 없을까란 생각에 검색을 해보았습니다.

덕분에 다음과 같은 방법을 찾을 수 있었습니다.

 

분해합을 통해 세자리의 정수 N(3)을 생성할 수 있는 생성자 M이 있습니다.

이들의 관계를 일반화해서 수식으로 나타내면 다음과 같습니다.

 

N(3) = M + m1 + m2 + m3

 

그리고 이항을 하면 다음과 같은 식이 나옵니다.

 

N(3) - (m1 + m2 + m3) = M

 

이때 각 3자리의 합이 최대가 되도록 하는 정수가 존재합니다. 바로 9+9+9 입니다.

즉, 입력받은 정수 N에 대하여 자리수만큼 9를 빼주면 됩니다.

그 미만의 정수는 N의 생성자가 될 수 없기 때문입니다.

 

따라서 N - (M의 길이 * 9)부터 탐색을 시작하면 됩니다.

 

두 번째 시도)

 

import java.util.Scanner;

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

        // 입력된 N의 길이를 알기 위해 string으로 입력
        String str_N = sc.nextLine();
        int N_len = str_N.length();
        // string to int
        int N = Integer.parseInt(str_N);
        int result = 0;

        // 생성자가 될 수도 있는 최소값인 N - (N의 자리수 * 9)부터 시작
        for(int i = (N - (N_len*9)); i < N; i++) {
            int number = i;
            int sum = 0;

            while(number > 0) {
                sum += number % 10;
                number/= 10;
            }

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

 

위의 코드를 백준에 제출했을 때 32ms가 단축된걸 알 수 있었습니다.

 

 

정리)

초기 프로그램을 작성하는 데에 많은 시간을 할애하지 않았지만 그럼에도 불구하고 프로그램의 효율을 최적화 할 수 있는 방법들이 여럿 존재한다는 것을 알 수 있었습니다.