솜이의 데브로그

백준 2231번 ) 분해합 (java) 본문

Algorithm/백준

백준 2231번 ) 분해합 (java)

somsoming 2022. 2. 24. 01:32

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

 

2231번: 분해합

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이

www.acmicpc.net

 

문제

 

풀이

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

public class BOJ_2231 {
    public static int solution(int n){
        for(int i = 0; i<n; i++){
            int sum = i;
            int number = i;
            while(number != 0){
                sum += number % 10;
                number /= 10;
            }
            if(sum == n) return i;
        }
        return 0;
    }

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

        int N = Integer.parseInt(br.readLine());
        
        System.out.println(solution(N));
    }
    
}

 

완전탐색문제로, 0부터 n 까지 계속해서 탐색해나가며 생성자인지 탐색하는 방식으로 한다.

찾아보니 0부터 찾을 필요는 없고, (n의 길이)*9 부터 탐색해 나가는 방식으로 하면 탐색의 수를 조금 더 줄일 수 있다.

 

for(int i = N- (N_length * 9); i < N; i++){
	...
}

이런식으로!

 

 

느낀점

완전탐색 문제가 나오면 효율적인거 따지다가 완전탐색 문제인지 모를 것 같다.

이런식으로 풀어야하는 문제인지 감을 늘리려면 많이 풀어봐야할 것 같다.