문제 번호 2231번 : 분해합 - JAVA [자바]

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

2231번: 분해합

 

문제 설명

 

주어진 수와 그 수의 각 자리수를 더했을 때 나오는 값을 입력했을 때 주어진 수를 구하는 문제입니다. 

 

문제 풀이

 

이 문제는 간단합니다. 해당 1~해당 수 만큼 반복해서 모두 비교해보면 됩니다!

저는..진짜 이 방법일주는 몰랐습니다. 해당 문제가 브루트 포스 문제라는 것과 주어진 시간이 2초라고 봤을 때 눈치 챘어야 됐는데..

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int result = 0;

        for(int i=1; i<n; i++){
            int sum = 0;
            int number = i;
            while(number != 0){
                sum += number%10;
                number = number/10;
            }

            if(sum+i == n){
                result = i;
                break;
            }
        }

        System.out.println(result);
    }
}

 

위에 코드를 보면 간단합니다. 1부터 각자리 수를 더한 값 SUM를 i값과 더해 주어진 숫자가 맞으면 반복문을 탈출하여 생성자를 맞추면 된는 문제입니다.

 

 

 

여기서 한번 더 생각하면 조금 시간을 줄일 수 있습니다. 

i의 최솟값을 구해보는 것입니다.

N(자리수) 일 때 

N(4) = K + K(1) + K(2) + K(3) + K(4) 일 것입니다.

물론 K + K(1) + K(2) + K(3) 일 수도 있을 것입니다. 하지만 그건 중요한게 아닙니다. 

3자리 보다 4자리가 더 큰 수이고 최소 K를 구하는 것에는 문제가 없습니다.

K = N(4) - (K(1) + K(2) + K(3) + K(4))가 될 것입니다.

그렇다면 각 자리수의 가장 큰 값은 무엇이 올 수 있을까요?

바로 9가 올 수 있습니다.

즉, K = N(4) - (9+9+9+9)보다는 큰 수를 가지고 된다는 것입니다.

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int result = 0;
        int nLength = (int)(Math.log10(n)+1);//값의 자릿수

        for(int i=(n-(9*nLength)); i<n; i++){
            int sum = 0;
            int number = i;
            while(number != 0){
                sum += number%10;
                number = number/10;
            }

            if(sum+i == n){
                result = i;
                break;
            }
        }

        System.out.println(result);
    }
}