[브루트포스] 백준 - 분해합

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

2231번: 분해합

 

-문제해설

맨 처음에는 1부터 입력된 값까지 반복문으로 순회하면 분해합을 구했는데 

범위를 축소시킬 수 있었다. 예를들어 입력된 값이 네 자리 정수 K라고하고 K의 생성자를 W라고 하면

 

K = W + W1 + W2 + W3 + W4 가 될 것이다. 이때 W의 각 자리수를 모두 좌변으로 넘기면

K - (W1 + W2 + W3 + W4) = W가 된다.

 

즉 K의 생성자인 W는 K - (W1 + W2 + W3 + W4) 보다는 커야 된다.

이때 K - (W1 + W2 + W3 + W4)가 가장 큰 값은 W의 자리값이 모두 9일 때이다.

즉, K - (9 + 9 + 9 + 9) 이다.

 

따라서 K - ( 9 * K의 자리수) = K - ( 9 * 4 ) 가 된다.

 

그래서 반복문을 K - ( 9 * 4 )부터 n까지 순회하면 된다.

 

첫 번째 자바코드는 int를 String으로 바꾸고 각 자리값을 charAt( index ) - '0' 을 통해서 다시 int로 만들어서 자리값의 합을 구하는 코드이다.

 

두 번째 자바코드는 수학적으로 1의 자리, 10자리, 100자리 .... 의 합을 구하는 코드이다.

 

메모리상으로는 수학적 풀이가 효율이 좋았고

시간상으로는 문자열 풀이가 효율이 좋았다.

 

파이썬은 수학적으로 풀었다.

 

 

-자바(문자열로 나눠서 분해합 구하기)

package math;

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

public class BJ2231 {
	private static BufferedWriter bw = 
			new BufferedWriter( new OutputStreamWriter(System.out));
	private static int n, sum, res;
	private static String tmp = "";

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt( br.readLine() );
		
		tmp = String.valueOf( n );
		
		int len = n-(tmp.length()*9);
		if( len <= 0 ) len = 1;
		
		for( int i=len; i<n; i++ ) {
			tmp = String.valueOf( i );
			
			sum = i;
			for( int j=0; j<tmp.length(); j++ ) sum += tmp.charAt(j)-'0';
			
			if( n == sum ) {
				res = i;
				break;
			} else continue;
		}
		bw.write( res + "\n" );
		bw.flush();
		bw.close();
		br.close();
	}
}

 

-자바(수학적으로 분해합 구하기)

package math;

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

public class BJ2231_1 {
	private static BufferedWriter bw = 
			new BufferedWriter( new OutputStreamWriter(System.out));
	private static int n, sum, res;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt( br.readLine() );
		
		String tmp = String.valueOf( n );
		int len = n-(tmp.length()*9);
		if( len <= 0 ) len = 1;
		
		for( int i=len; i<n; i++ ) {
			int num = i;
			
			sum = 0;
			while( num != 0 ) {
				sum += num%10;
				num /= 10;
			}
			if( sum+i==n ) {
				res = i;
				break;
			}
		}
		
		bw.write( res + "\n" );
		bw.flush();
		bw.close();
		br.close();
	}
}

 

 

-파이썬

n = int(input())
l = n - ( len( str(n) ) * 9 )
if l <= 0:
    l = 1
res = 0

for i in range( l, n ):    
    num = i
    s = 0
    while num != 0:
        s += num%10
        num //= 10
    if s+i == n:
        res = i
        break
        
print( res )