[JAVA] 백준 2231번 : 분해합

28 Apr 2022 in Blog / Algorithm / Bronze II / Bronze-ii on Algorithm, Baekjoon, Bronze

안녕하세요, 해을입니다🦖

이번 글에서는 백준 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을 출력한다.

💡 예제 입력 1

216

💡 예제 출력 1

198

🚩 문제 풀이

[주어진 값]

• 자연수 : N

[구해야 할 값]

• N의 가장 작은 생성자

---

1부터 N까지 한개씩 모두 대입해보는 브루트포스 방식을 이용하여 문제를 해결합니다.

생성자의 최솟값을 구하기 위해 작은 수부터 반복문을 실행합니다.

만약 생성자가 없다면 0을 출력합니다.

심화 풀이

생성자의 최솟값을 구하면 1부터 반복하지 않아도 됩니다.

가능한 최솟값을 구하기 위해 분해합의 정의와 예시를 다시 살펴보겠습니다.

• M의 분해합 = N = M + M_각자릿수의합
• 245의 분해합 = 256 = 245 + 2 + 4 + 5

이를 수식으로 나타내면 다음과 같습니다. (ex : 세자릿수 정수 N 입력) \[N(3) = M + M_1 + M_2 + M_3\] \[N(3) - (M_1 + M_2 + M_3) = M\]

이때 각 자릿수의 합이 최대인 경우는 (9 + 9 + 9)이므로

입력받은 정수 N의 자릿수 길이만큼 9를 뺀 미만의 수들은 생성자가 될 수 없다는 것을 알 수 있습니다.

따라서, 1부터가 아닌 N - (M의 길이 * 9)부터 N까지 탐색하면 됩니다.

import java.util.*;

public class Main {
 public static void main(String[] args) {  
  Scanner sc = new Scanner(System.in);
  
  String str_N = sc.nextLine();
  
  int N = Integer.parseInt(str_N);
  int M = 0;
  
  for(int i = ( N- (str_N.length() * 9) ); i<=N; i++) {
   int num = i;
   int sum = 0;
   
   while(num != 0) {
    sum += num%10;
    num /= 10;
   }
   
   if(sum + i == N) {
    M = i;
    break;
   }
  }
  
  System.out.println(M);
  
  sc.close();
 }
}

🚩 소스 코드

import java.util.*;

public class Main {
 public static void main(String[] args) {  
  Scanner sc = new Scanner(System.in);
  
  int N = sc.nextInt();
  int M = 0;
  
  // for(int i = (N - (N.le)))
  for(int i = 1; i<=N; i++) {
   int num = i;
   int sum = 0;
   
   while(num != 0) {
    sum += num%10;
    num /= 10;
   }
   
   if(sum + i == N) {
    M = i;
    break;
   }
  }
  
  System.out.println(M);
  
  sc.close();
 }
}

---

오류 및 오타 지적, 질문, 인사 등 무엇이든 언제나 환영입니다!

읽어주셔서 감사합니다.

끝!🦕