[백준] 2231번 : 분해합 - Java

https://www.acmicpc.net/problem/2231

2231번: 분해합

---

---

알고리즘 - 브루트 포스

정의

• 난폭한(무식한) 힘
• 무차별적 대입 방법

특징

• 가능한 모든 경우의 수 대입 ➡ 조건에 만족하는 값만을 찾아냄
• 자원만 충분하다면 원하는 값을 100% 확률로 찾을 수 있음
• "빠짐 없이" 완전탐색 알고리즘을 잘 설계하는 게 핵심

---

구현 방법

1. 예제

//예제1 - 198
198 + 1 + 9 + 8 = 216
198 = 생성자
216 = 198의 분해합

//예제2 - 216
198 + 1 + 9 + 8 = 216
207 + 2 + 0 + 7 = 216

• 216 처럼 여러 생성자 존재할 수 있음
• 생성자 : 1개 이상 ➡ 작은 수부터 찾아야 최소값 찾을 수 있음

 

2. 응용

2.1. 기본 브루트 포스 방식

• 1 부터 ~ 입력 받은 N 까지 한 개씩 모두 대입

2.2. 임의의 수 N = K + (K의 각 자릿수의 합)

K의 각 자릿수의 합이 가장 큰 경우 = 9 + 9 + 9 + 9
➡ 입력 받은 정수 N 에 대해 자릿수의 길이만큼 9 빼주기
= 그 미만의 수는 생성자 될 수 없음

최적화된 탐색 범위
N - (9 x K의 길이) 부터 ~ N 까지만 탐색

---

풀이

1. Scanner

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
 
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int result = 0;
		
        for(int i = 0; i < N; i++) {
            int number = i;
            int sum = 0; //각 자릿수의 합
			
            while(number != 0) {
                sum += number % 10; //각 자릿수 더하기
                number /= 10;
            }
            //i 값 + 각 자릿수의 누적합 = N (생성자 찾은 경우)
            if(sum + i == N) {
                result = i;
                break;
            }
        }
        System.out.println(result);
    }
}

 

2. BufferedReader + StringTokenizer

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {
    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;
            }
            //i 값 + 각 자릿수의 누적합 = N (생성자 찾은 경우)
            if(sum + i == N) {
                result = i;
                break;
            }
        }
        System.out.println(result);
    }
}

---

3. Scanner + 조건문

• N - (9 x K의 길이) 부터 ~ N 까지만 탐색

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
    
        Scanner in = new Scanner(System.in);
    
        //자릿수의 길이값 알기 위해 문자열로 받기
        String str_N = in.nextLine();
 
        //해당 문자열 길이
        int N_len = str_N.length();
 
        //String ➡ int
        int N = Integer.parseInt(str_N);
        int result = 0;
		
        //탐색 범위
        //가능한 최솟값인 (N - 9 * N) 의 각 자릿수 ~ N 까지
        for(int i = (N - (N_len * 9)); i < N; i++) {
            int number = i;
            int sum = 0; //각 자릿수 합
			
            while(number != 0) {
                sum += number % 10;//각 자릿수 더하기
                number /= 10;
            }
            //i 값 + 각 자릿수의 누적합 = N (생성자 찾은 경우)
            if(sum + i == N) {
                result = i;
                break;
            }
        }
        System.out.println(result);
    }
}

 

4. BufferedReader + StringTokenizer + 조건문

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {
    public static void main(String[] args) throws IOException {
    
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
        //자릿수의 길이값 알기 위해 문자열로 받기
        String str_N = br.readLine();
 
        //해당 문자열 길이
        int N_len = str_N.length();
 
        //String ➡ int
        int N = Integer.parseInt(str_N);
        int result = 0;
 
        //탐색 범위
        //가능한 최솟값인 (N - 9 * N) 의 각 자릿수 ~ N 까지
        for(int i = (N - (N_len * 9)); i < N; i++) {
            int number = i;
            int sum = 0; //각 자릿수 합
			
            while(number != 0) {
                sum += number % 10;//각 자릿수 더하기
                number /= 10;
            }
            //i 값 + 각 자릿수의 누적합 = N (생성자 찾은 경우)
            if(sum + i == N) {
                result = i;
                break;
            }
        }
        System.out.println(result);
    }
}

---

성능

• BufferedReader > Scanner

 

---

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