[백준] 2231번: 분해합 (Java)

1. 문제설명

어떤 자연수 M이 있을 때 M과 M을 이루는 각 자리수의 합을 분해합 N이라고 한다. M은 N의 생성자라고 한다. 자연수 M이 주어졌을 때, N의 가장 작은 생성자를 구하는 문제이다.

• 시간 제한: 2초
• 메모리 제한: 192MB

 

2. 접근 방식

=> 완전탐색을 이용해 1부터 시작하여 N의 가장 작은 생성자를 찾는다.

• while 문을 이용해 1부터 분해합(`sum`)을 구한다.
• 첫 번째 while 문 종료 조건:
  • `sum`이 N이면 `result`에 해당 숫자를 저장하고 종료
  • 해당 숫자가 N이 되면 종료 (생성자를 찾을 수 없기 때문에 `result`는 0이 됨)

 

3. 최종 코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int result = 0; // 결과값 (생성자가 없는 경우: 초기값 0)
        int num = 1; // 1부터 시작하여 모든 가능한 숫자를 검사
        
        while(num < N) { // N보다 작은 숫자를 검사
            int cal = num; // 분해합 계산을 위해
            int sum = cal; // 먼저 자기 자신으로 분해합 초기화
            while(cal > 0) { // 각 자리수를 더함
                sum += cal % 10; // 일의 자리수
                cal /= 10;
            }

            if(sum == N) { // 계산한 분해합이 N과 같으면
                result = num; // 현재 숫자를 결과값으로 저장
                break; // while문 종료
            }
            num++; // 다음 숫자
        }
        System.out.println(result);
    }
}

 

4. 시간복잡도

• 외부 while문: $O(N)$
• 내부 while문(숫자의 자리수): $O(log N)$

따라서 전체 시간복잡도는 $O(N * log N)$ 이다.