백준 2231번 분해합 (JAVA)

 📌문제   

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

 

 📌해설&답  

💡해설

  idea)  
1. 1부터 주어진 수 n까지 전부 탐색해보면 비효율적이므로, 가능한 수부터 탐색한다.
2. 분해합을 계산할 때 계산할 숫자 m의 각 자리수의 최댓값은 9이다.
   (111 → 1+1+1=3,  999 → 9+9+9=27)
3. 주어진 수 n의 자리수가 j개라면, 자리수의 합의 최댓값은 9*j이다.
   (2345는 4자리(j=4) → 4자리수의 최댓값은 숫자가 9999일 때이고, 자리수의 합의 최댓값은 9+9+9+9 = 9*4 = 36 )
4. 따라서 생성자는 최소 (n-9*j)이상이어야 한다.
  (259 → n=259, j=3 이므로 259 - 9*3 = 232 이상의 숫자에 생성자가 존재한다.)
5. 생성자로 계산한 이 n-9*j 값이 음수가 되는 경우를 생각해, 1과 n-9*j중 작은 값부터 탐색을 시작한다.
  (n=17 일 때, n-9*j = 17-9*2 = -1 이므로 n-9*j부터 탐색을 시작해선 안된다.) 

 

 

💡답

import java.io.*;

public class Main {
    /**
     * n : 주어진 수
     * m : n의 생성자
     * j : n의 길이 (몇 자리 수인지)
     * sum: 분해합(m과 m의 각 자리의 합을 저장할 변수)
     * i : 생성자인지 아닌지 판단하기 위해 테스트 해 볼 숫자
     */
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String v = br.readLine();
        int j = v.length();
        int n = Integer.parseInt(v);
        int a = 0;
        int sum = 0;
        int k = 0;
        for (int i = Math.max(n-9 * j, 1); i < n; i++) {
            sum = i;
            k = i;
            while (k > 0) { //i의 각 자리수를 쪼개서 sum에 더하는 과정 (ex:123이면 1+2+3)
                sum += k % 10;
                k /= 10;
            }
            if(sum == n) { //i의 분해합이 n과 같다면 계산을 멈춘다.
                a = i;
                break;
            }
        }
        System.out.println(a);
    }
}

 

 

 

 📌코멘트  

 

1. 어떻게 하면 더 성능이 좋을지 항상 고민하자.

2. 주석을 열심히 달자...

 

 

 

 

끝까지 읽어주셔서 감사합니다 :)

Have a good day🐱

 

---

📢

1. 개발자 준비생이 공부한 내용을 정리한 글입니다. 내용에 오류가 있을 수 있습니다.
2. 위와 같은 이유로 내용에 대한 지적과 조언은 감사하게 받습니다.
3. 이 글의 내용은 계속 공부함으로써 언제든지 추가/수정 될 수 있습니다.