[Java] 백준알고리즘 #2231 분해합

백준알고리즘 #2231 분해합 문제

어떤 자연수 n이 있을 때 n과 n의 각 자리수를 더한 것을 분해합이라고 하고, 이 분해합을 A라고 할 때 n은 A의 생성자가 된다고 한다.

임의의 자연수 n, 즉 분해합 n이 주어졌을 때 생성자 m을 구하는 문제이다.

 

각 자리수를 더하는 방법만 알고 있다면 아주 쉽게 해결 할 수 있는 문제이다.

임의의 정수 i가 있을 때 각 자리수를 더하는 방법은 다음과 같다.

while(i > 0){
	sum += i % 10;
	i = i / 10;
}

합을 저장할 sum변수에 i를 10으로 나눈 나머지를 넣은 후 다시 i에 i를 10으로 나눈 몫을 저장한다.

만약 789라면

 

1. 798를 10으로 나눈 나머지인 9가 sum에 저장됨

2. i에  789를 10으로 나눈 몫인 78이 저장됨

3. 78을 10으로 나눈 나머지인 8과 sum을 합친 값이 sum에 저장됨

4. i에 78을 10으로 나눈 몫인 7이 저장됨

5. 7을 10으로 나눈 나머지인 7과 sum을 합친 값이 sum에 저장됨

6. 7을 10으로 나눈 몫인 0이 i에 저장됨

7. i가 0으로  i > 0 조건에 부합하지 않으니 while문을 빠져나옴

 

위와 같은 순서대로 while문을 반복할 것이다.

이를 위 문제에 대입해보면 다음과 같다.

int n = sc.nextInt();
int check = 0;
for (int i = 0; i < n; i++) {
	int con = i;
	int sum = con;
	while (con > 0) {
		sum = sum + con % 10;
		con = con / 10;
	}
	if (sum == n) {
		check++;
		System.out.println(i);
		break;
	}

}

분해합은 생성자보다 클 수 밖에 없으므로 범위를 i < n까지로 한정해두고 for문을 반복하여 i가 n의 생성자인지 판단한다.

반복하는 i를 con이라는 변수에 복사하여 위의 자리수를 더하는 while문을 통과시키면

sum에는 i에 대한 분해합이 저장된다.

이 sum이 기존에 주어진 수 n과 같다면 check(생성자 수 유무를 판별하는 변수) 를 증가시킨 후 i를 출력시킨 다음 반복문을 빠져나가면 된다.

여기서 check변수는 생성자가 0개인 경우를 따로 출력해주기 위해 만들어두었다.

 

전체 코드를 보면 다음과 같다.

import java.util.Scanner;

public class Back2231 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int check = 0;
		for (int i = 0; i < n; i++) {
			int con = i;
			int sum = con;
			while (con > 0) {
				sum = sum + con % 10;
				con = con / 10;
			}
			if (sum == n) {
				check++;
				System.out.println(i);
				break;
			}

		}
		if (check == 0)
			System.out.println(0);

	}

}