[알고리즘] 백준문제풀이2231_분해합
브루트포스
알고리즘 유형 정리
브루트포스 란
완전탐색 알고리즘. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.
이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다.
- 알고리즘 설계의 가장 기본적인 접근 방법은 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법이다.
- 선형 구조를 전체적으로 탐색하는 순차 탐색, 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS, Depth First Search)과 너비 우선 탐색(BFS, breadth first search)이 가장 기본적인 도구이다.
너비 우선 탐색은 브루트 포스와 관련이 깊고, 깊이 우선 탐색은 다음에 작성될 백트래킹과 관련이 깊으므로 그때 따로 작성하도록 하겠다.
문제풀이
-
문제
어떤 자연수 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을 출력한다 -
예제입력 :
216
예제출력 :
198
import java.util.Scanner;
public class 백준2231_분해합 {
static int result = Integer.MAX_VALUE;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int M = sc.nextInt();
solution(M);
System.out.println(result);
}
public static void solution(int M) {
boolean 존재 = false;
for(int i=1; i <M ; i++) {
int[] arr = new int[10];
int 자연수 = M- i;
int 초기값 = 자연수;
int idx =0;
do {
int 나머지 = 자연수 % 10;
자연수 = 자연수 / 10;
arr[idx++] = 나머지;
}while(자연수 !=0);
int sum = 초기값 ;
for(int j=0; j<idx ; j++) {
sum += arr[j];
}
if(sum == M && 초기값 < result ) {
result = 초기값;
존재 = true;
}
}
if(!존재) {
result = 0;
}
}
}
해설
주어진 수부터 한개씩 차감하여 0이 될때까지의 모든 수에 대해 부분합을 구한 후 부분합이 성립되는 가장 작은 자연수를 구하는 식으로 풀이하였다. 부분합이 성립되는 규칙을 생각하지않고 단순하게 풀이했을 때는 이렇게 풀면되지만 시간이 오래걸린다.
실제 시간이 264ms
가 소요되었다.
조금 더 최적화된 탐색을 위해 아래와 같이 함수 구조를 변경하였다.
public static void fastSolution(int M,String M_str) {
int init = M - (9* M_str.length());
boolean 존재 = false;
for(int i=init; i <M ; i++) {
int 자연수 = i;
int sum = i ;
do {
int 나머지 = 자연수 % 10;
자연수 = 자연수 / 10;
sum += 나머지;
}while(자연수 !=0);
if(sum == M ) {
result = i;
존재 = true;
break;
}
}
if(!존재) {
result = 0;
}
}
생성자가 가능한 최소 수는 각자리수가 9일때가 최솟값이기 때문에 i가 0부터 순환하는게 아닌 생성자가 가능한 최소 수부터 탐색하여 탐색횟수를 줄일 수 있다.
위와같이 변경하여 실행하게 되면 속도는 196ms
로 조금 더 빨라짐을 확인할 수 있다.