[백준 온라인저지]분해합 - 브루트포스(2)

분해합

이번 포스팅 문제는 2231번 문제입니다. 이 문제 역시 브루트포스 알고리즘을 통해 해결하였습니다.

그럼 문제를 풀어보도록 하겠습니다

문제요약

자연수 n이 주어졌을 때 자연수n의 생성자 중 최소값을 구하는 문제입니다.

어떤 자연수 n의 분해합이 m일 경우 m을 n의 생성자라 합니다. 분해합은 자신과 각 자리수의 합을 말합니다. 

예를 들어 자연수 256은 분해합 245를 가지는데 그 이유는 256 = 245 + 2 + 4 + 5 이기 때문입니다. 

풀이전략

1. 생성자의 최소값을 구하는 문제이고 생성자는 n보다 클수가 없기때문에 1부터 n까지 반복문을 실행합니다.

2. 해당 자연수가 생성자라고 판별되면 그 값이 생성자의 최소값입니다.

구현하기

package BackJoon.브루트포스;
 
import java.util.Scanner;
 
/**
 * https://www.acmicpc.net/problem/2231
 * @author troh
 *
 */
public class _2231_분해합 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(getMinConstructor(n));
    }
    
    private static int getMinConstructor(int n) {
        int min = 0;
        for(int i=1; i<n; i++) {
            boolean isConstructor = isConstructor(n, i);
            if(isConstructor) {
                min = i;
                break;
            }
        }
        return min;
    }
    
    private static boolean isConstructor(int n, int m) {
        // sum을 m으로 초기화한 후 1의자리수부터 sum에 더한 다음 최종적으로 n과 같은지 확인함
        int sum = m;
        while(m/10 != 0) {
            sum = sum + (m % 10);
            m = m / 10;
        }
        sum = sum + (m % 10);
        return sum == n ; 
    }
}
 

배운점

제가 생각하는 문제의 핵심은 

• 생성자는 n보다 클 수 없고 최소값을 찾는 문제이기 때문에 1 -> n까지 반복문을 실행하고 처음 찾는 생성자가 최소값이라는 점
• 각 자리수를 더하는 알고리즘

이정도 인 것 같습니다. 가장 큰 자리수부터 더하려고 했는데 자리수를 구해야하고 알고리즘이 복잡해지는 것 같아 관점을 바꿔서

1의 자리수부터 더하도록 수정했습니다.