알고리즘 문제풀이 - 백준#2231번: 분해합

 

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

2231번: 분해합

숫자 n을 받아서

-1을 하면서 분해합에 맞는 수를 찾기..

라는 방법은 다들 떠올렸을테고

 

이걸 더 효율적으로 구하는 법:

수가 얼마가 됐든

각 자리의 최대는 9다

216의 분해합을 구해도 9+9+9.. 27을 넘지 않고

216524의 분해합을 구해도 9+9+9+9+9+9... 54를 넘지 않을 것.

그러니까 처음에 받은 수 n에서 

n의 자릿수 * 9를 한만큼 빼고

그 수에서 n까지 비교하면 더 짧은 시간내에 답을 구할 수 있다.

예) 216이면 216-27을 하고 189에서 216까지 비교한다.

 

 

import java.util.Scanner;

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

		int n = scan.nextInt();
		int length = (int) (Math.log10(n) + 1);
		int result=0;
		for (int i =(n-(length * 9)); i <n; i++) {
			int number = i;
			int sum = 0;

			while (number != 0) {
				sum += number % 10;
				number /= 10;
			}

			if (sum + i == n) {
				result=i;
				break;
			}
		}
		System.out.print(result);
	}
}