[Dev-Ping9] 백준 2231번 - 분해합 (Java)

 

헐... 21등 했어요... 🥺🥺🥺

 

# 문제설명

[Base Description]

 생성자가 여러개 있을 수 있음 -> 모든 경우를 탐색해야 한다 -> 그 중에 가장 작은수를 찾아야함

 

[N의 최대 값인 1백만으로 가정]

 >> 찾아지는 생성자(m)은 상당히 큰 수 일 것이 자명 

 >> 0에서 N까지 탐색하는 방법은 상당히 비효율적

 >> 일정범위 이하로는 탐색할 필요가 없을 것이 자명

[어디까지를 탐색범위로 제한할 것인가?]

 >> N = m + sub(m) 

 >> sub(m) 은 아무리 크더라도, N의 자릿수갯수 * 9 이하

 >> sub(m) 을 최대값으로 가정했을때 만족하는 m 이하로는 탐색할 필요가 없음 (반대로 말하면, 해당 m보다 큰값만 탐색하면 됨)

 

---

# 코드구현

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

public class Main{
    static int ans;
    public static void dfs(int n, int m){

        char[] nums = String.valueOf(m).toCharArray();        
        if(n>nums.length*9+m) return;
        
        int sum =m;
        for(char i : nums){ // 각자릿수 합
            sum+=(i-'0');
        }
        if(n == sum){
            ans = m;
        }
        dfs(n,m-1);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        //n이 주어졌을때 n의 생성자.. -> m + m의 각자리수 합
        //각 자릿수는 10보다 작기때문에, 자리수 갯수가 k일때, 각자릿수합은 9*k 이하
        //그러니까 숫자가 큰것에서 내려가면서 탐색하면 금방찾음
        //근데 가장작은 생성자를 찾아야함. 어디까지를 기준으로 잡아야하나.. n/2? 
        //음,,, 100이하는 풀탐색하고 그다음부터는 n/2까지 돌릴까?
        //n <=1_000_000 ... -> 완전탐색시 1백만 -> 최대자릿수 7개 -> 합은 63보다 작음 -> m + sub(m) 
        // n= m + 최대합 ...!       
        
        dfs(n,n-1);
        System.out.println(ans);
    }
}