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

 

 

 

---

⬛ 문제

 

 

https://www.acmicpc.net/problem/2231

2231번: 분해합

 

 

 

---

⬛ 풀이

 

전형적인 브루트포스 문제이다. 

 

1 이상 1,000,000 이하인 자연수 N이 주어졌을 때 N의 가장 작은 생성자를 구해야 한다. 

어떤 자연수 M의 분해합이 N일 때 M은 N의 생성자이다. (ex. 245의 분해합 = 245 + 2 + 4 + 5)

 

1,000,000은 생성자가 없기 때문에 N은 최대 6자리 자연수이다.

 

따라서 생성자를 M이라 할 때 N = M + ☆ + ☆ + ☆ + ☆ + ☆ + ☆ (☆은 M의 각 자리수)이고 ☆은 0~9 사이 이므로 M의 범위는 N-54 <= M < N이 된다.

 

최대 54개의 숫자의 분해합을 구해 N과 비교하여 같다면 해당 값을 같은 숫자가 없다면 0을 리턴한다.

 

 

 

---

⬛ 코드

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		FindConst(n);
	}
	
	public static void FindConst(int n) {
		for (int con = n - 54; con < n; con++) {
			int c = con;
			int sum = c;
            
			while (true) {
				sum+=c%10;
				c/=10;
				
				if(c==0)
					break;
			}
			
			if(sum==n) {
				System.out.println(con);
				return;
			}
		}
		System.out.println(0);
	}
}