[백준] 2231.분해합(Java8)

 문제 

 풀이 

package solved2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException{
		//분해합(부르트포스)
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String strN = br.readLine();
		int n = Integer.parseInt(strN);
		int sum = 0;//각 자릿수의 합
		int su;
		
		for(int i = n - 9 * strN.length(); i < n; i++) {
			su = i;
			sum = su;
			while(su != 0) {
				//각 자릿수의 합 구하기
				sum += su % 10;
				su /= 10;
			}
			if(sum == n) {
				//생성자인 경우
				System.out.println(i);
				return;
			}
		}
		System.out.println(0);
		
		br.close();

	}

}

 팁 

[부르트 포스 알고리즘]

brute: 무식한, force: 힘의 뜻을 가지고 있다.완전탐색 알고리즘으로 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.
문제를 해결하기 위해서, 가능한 모든 경우에 대해 모두 직접 해보는 방법이다.

자료의 구조에 따라서 브루트포스는 2종류로 나뉘게 된다.

• 선형구조 - 순차탐색
• 비선형구조 - BFS, DFS

[ 생성자의 최솟값 찾기 ]

4자리의 자연수 N을 입력받은 경우, 최솟값은 N - (9 * 4)인 것을 알 수 있다.

즉, 생성자의 최솟값인 N - (9 * K의 길이)부터 N까지 탐색하면 속도를 높일 수 있다.

 출처 

2231번: 분해합