[백준] no2231: 분해합

문제

: 입력된 숫자(N) = 입력된 숫자보다 작은 숫자(M) + M의 각 자릿수의 숫자의 합

 

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

---

원리

1. 브루트 포스: 해당 수가 나올때까지 1씩 더해가며 경우의 수 반복

2. 입력된 숫자의 자릿수*9 + M 밑으로는, M + M의 각 자리수의 합을 해도 절대 N이 나올수가 없음

  (왜냐하면 모든 자릿수 중 제일 큰 수인 9보다 낮은 수가 나올것이기 때문)

 

---

나의 코드

1. 브루트포스로 N부터 -1씩 낮춘 수로 구하기 + N보다 최대 2자리수 밑으로는 암만 더해도 N이 될 수 없음

: 500ms | 142288kB (비추천)

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

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

        int T = Integer.parseInt(br.readLine());
        String strT = String.valueOf(T);
        int num = 1;
        int result = 0;
        while(true) {
            int base = T-num;
            if(base==0) {
                break;
            }
            String baseStr = String.valueOf(base);
            if(strT.length()>=3 && baseStr.length()<=strT.length()-1) break;
            ArrayList<Integer> list = new ArrayList<>();
            for(int i=0;i< baseStr.length();i++) list.add(Character.getNumericValue(baseStr.charAt(i)));
            for(int i=0;i< list.size();i++) base += list.get(i);
            if(base==T) {
                result = Integer.parseInt(baseStr);
            }
            num++;
        }
        System.out.println(result);
    }
}

---

레퍼런스 코드

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

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

        // i 는 가능한 최솟값인 N - 9 * N의 각 자릿수부터 시작
        for(int i = (N - (str.length() * 9)); i < N; i++) {
            int number = i;
            int sum = 0;   // 각 자릿수 합 변수

            while(number != 0) {
                sum += number % 10;    // 각 자릿수 더하기
                number /= 10;
            }

            // i 값과 각 자릿수 누적합이 같을 경우 (생성자를 찾았을 경우)
            if(sum + i == N) {
                result = i;
                break;
            }
        }
        System.out.println(result);

    }
}

 

참고 링크 : https://st-lab.tistory.com/98