알고리즘 풀이(JAVA) - 백준 알고리즘_2231(브루트포스-분해합)

By on September 8, 2019

브루트포스(brute-force)

  • 브루트포스란?
    brute는 “짐승같은, 난폭한”이라는 뜻이고, brute-force는 “난폭한 힘, 폭력”이라는 뜻이다. 암호학 용어로는 brute-force attack 또는 exhaustive key search, 우리말로는 노가다 또는 무차별 대입 공격이라 부른다. 주로 암호학에서도 쓰이는 방법이긴 하지만, 굳이 암호학만의 문제는 아니고 다른 알고리즘 분야에서도 사용되고 있다. 간단하게 말하자면 노가다와 다굴을 논리적이고 과학적으로 하는 방식.

  • 특징
    조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 문제를 푸는 것인데, 얼핏 무식하다고 생각할 수도 있겠지만 성공한다는 가정 하에 항상 정확도 100%를 보장한다는 점에서, 자원만 충분하면 가장 무서운 방법이다. 이론적으로 가능한 모든 경우의 수를 다 검색해 보는 것이라 정확도 100%가 항상 보장되니, 암호학에서는 가장 확실한 방법으로 통용되고 있다. 무엇보다도 암호 확인 작업이라는 것이 손으로 입력한 문자열의 동일 여부를 확인하는 것이기 때문에, 가능한 경우를 하나씩 대입하다 보면 언젠가는 암호를 찾을 수 있게 되는 식이다. 다만 정말로 그냥 무식하게 때려박는 건 아니고, 숫자만 섞어서 대입해보기 한번, 로마자만 섞어서 대입해보기 한번 이런식으로 하다가 안되면 나머지를 순차적으로 하는 식으로 특정 규칙에 따라 우선순위를 두고 하기도 한다.

문제

문제 링크 : https://www.acmicpc.net/problem/2231

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다.
어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다.
물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다.
반대로, 생성자가 여러 개인 자연수도 있을 수 있다.

자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.

풀이

  • 입력된 값에서부터 시작 해서 숫자 하나씩 감소해 시킴.
  • 감소된 숫자를 한자씩 쪼개어 더함(분해합)
  • 분해합이 자연수 N과 같다면 결과 변수에 저장. 생성자의 최소값을 찾기 위해 반복함.
  • 생성자를 찾지 못했을 경우(flag==false) 0 을 출력, 찾았을 경우 최소값을 출력(minValue)

소스

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

public class Baekjoon_2231 {
	public static void main(String[] args){
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        try{
        	String N = reader.readLine();
        	separation(N);
        }catch(Exception e){
            e.printStackTrace();
        }
    }

	private static void separation(final String n) {
		int num = Integer.parseInt(n);
		int minValue = num;
		boolean flag = false;
		for(int i = num; i >= 0; i--) {
			if(num == sum(i)) {
				if(minValue > i) {
					minValue = i;
					flag = true;
				}
			}
		}
		if(!flag) {
			System.out.println(0);
			return;
		}
		System.out.println(minValue);
	}

	private static int sum(int num) {
		int result = num;
		char[] numArr = String.valueOf(num).toCharArray();
		for(int i = 0; i < numArr.length; i++) {
			result += Integer.parseInt(String.valueOf(numArr[i]));
		}
		return result;
	}
}

Back to blog