백준 - 2231 - 분해합

 

---

 

이 문제는 완전 탐색, 브루트 포스에 관한 문제이다.

 

완전 탐색, 브루트 포스란 무엇인가?

브루트 포스를 사전적 의미로 찾아본다면 다음과 같다.

 

브루트(Brute) : 무식한 + 포스(Force) : 힘

 

즉, 발생할 수 있는 모든 경우를 무식하게 탐색한다는 뜻이다.

전체를 탐색한다는 의미에서 전체 탐색, 완전 탐색이라고도 한다.

 

브루트 포스 알고리즘을 설계할 때는 해가 하나 이상 존재한다는 가정을 세우고 모든 범위를 탐색하기 때문에 무조건 정답을 찾을 수 있다.

 

* 장점

- 알고리즘을 설계하고 구현하기 매우 쉽다.

- 복잡한 알고리즘 없이 빠르게 구현할 수 있다.

 

* 단점

- 알고리즘의 실행 시간이 매우 오래 걸린다.

- 메모리 효율면에서 매우 비효율적이다.

 

# 브루트 포스의 종류

브루트 포스는 크게 선형 구조와 비선형 구조로 나눌 수 있다.

- 선형 구조 : 순차 탐색

- 비선형 구조 : 백트래킹, DFS, BFS

 

---

문제로 돌아가보자.

생성자의 경우 1개 이상이기 때문에 최솟값을 찾기 위해서는 작은 수부터 찾아야 한다.

가장 기본적인 방법은 1부터 입력받은 N까지 한 개씩 모두 대입해 보는 것이다.

 

1부터 N까지 for 문으로 도는 동안에 만약 i가 0이 아닌 동안 각 자릿수를 구하고 더한 다음에

각 자릿수와 i를 더한 값이 N과 같다면 결과에 i를 출력한다.

 

 

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

public class B_2231 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int result = 0;

        for(int i = 0; i < N; i++){
            int number = i;
            int sum = 0;

            while (number != 0){
                sum += number % 10;
                number /= 10;
            }

            if(sum + i == N){
                result = i;
                break;
            }
        }
        System.out.println(result);
    }
}

 

 

 

참고 블로그 : 

https://st-lab.tistory.com/98