[백준알고리즘-JAVA]2231번 풀이(분해합) - 초보도 이해하는 풀이

안녕하세요

인포돈입니다.

백준 알고리즘 2231번 풀이입니다. 


* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 2231(분해합)

문제

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자릿수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.

자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.

입력 예시

216

출력 예시

198

성공코드

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

public class Main {
	
	public static void main(String args[]) throws IOException{
	   	  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	   	 
	   	 	int num = Integer.parseInt(br.readLine());
	   
	   	 	int sum = 0;
	   	 	int digit = 0;
	   	 	
	   	 	for(int i = 0 ; i < num ; i++) {
	   	 	
	   	 		int tmp = i;
	   	 	
	   	 		while(true) {
	   	 		if(tmp == 0)
   	 			break;
	   	 	tmp = tmp/10;
   	 		digit++;
   	 		}
	   	 		tmp = i;
	   	 		sum = i;
	   	 		
	   	 		for(int j = 0 ; j < digit ; j++) {
	   	 			sum = sum + (tmp%10);
	   	 		    tmp = tmp/10;
	   	 		}
	   	 		
	   	 		if(sum == num) {
	   	 			sum = i;
	   	 			break;
	   	 			}
	   	 		
	   	 		sum = 0;
	   	 		digit = 0;
	   	 	}
	   	 
	   	 	
	   		System.out.println(sum == num ? 0 : sum);
		}
		}

4456ㅁㄹ5ㅁㅈㄷ1ㄻㅈㄷㄹ5ㅁㄴㅇㄻㄴㅇㄹ  분해합 알고리즘은 어떠한 방식으로 접근을 해야 될까요? 간단한 힌트는 바로 브루트 포스 방식으로 풀어야 한다는 겁니다.

 

일련의 문자열을 하나씩 검사하여 결론을 도출하는 방법으로 해당 숫자가 주어지면 해당 숫자까지의 모든 수들을 검사하여 결론을 도출해야 한다는 의미입니다.

 

그렇다면 분해합을 구하기 위해서 가장 중요한 것이 무엇일까요? 바로 자릿수입니다. 1, 10, 100, 1000 해당 합을 구하기 위해서는 1 / 10 + 1 + 0 / 100 + 1 + 0 + 0.... 이런 식으로 자릿수에 맞게 더해야 하는 수가 늘어나기 때문입니다.

 

해당 알고리즘을 풀기 위해 간단한 알고리즘 흐름도를 생각해보도록 하죠

 

---

알고리즘 흐름도

입력받기 -> 자릿수 판별하기 -> 판별한 자릿수로 반복하여 더해주기 -> 더해준 값이 입력해준 값이랑 같은지 판별 -> 맞으면 출력

 

---

STEP1 자릿수 판별하기

for(int i = 0 ; i < num ; i++) {
	   	 	
	  int tmp = i;
	   	 	
	  while(true) {
	   	 if(tmp == 0)
   	 	 break;
	   	 tmp = tmp/10;
   	 	 digit++;
   	 		}	
	   	 }

먼저 코드를 보여 드렸습니다. i가 1번부터 시작하여 입력받은 숫자 가지 반복하면서 digit이라는 변수에 자릿수를 표현하는 것입니다. temp에 i값을 넣어주고 ( i값이 변하면 안 되기 때문입니다.) 무한 루프를 돌며 tmp가 0이 되는 순간까지 반복하면서 digit을 1개씩 증가시키면 됩니다.

 

간단하죠? 만약에 1이 들어오면 temp/10을 하는 동시에 0이 되어 digit은 1이 되게 됩니다.

 

STEP2 판별한 자릿수로 반복하여 분해합 구하기

tmp = i;
sum = i;
	   	 		
	for(int j = 0 ; j < digit ; j++) {
	   	sum = sum + (tmp%10);
	   	tmp = tmp/10;
	   	 		}

앞서 tmp 변수는 i값을 넣어준 뒤 digit에 활용하였기에 다시 i로 초기화를 해줍니다. sum의 경우 만약에 10이라는 숫자가 있다면 10 + 1 + 0 이 분해합이 되겠죠? 그렇기 때문에 해당 값을 미리 넣어주는 작업이라고 생각하시면 됩니다.

 

ex) 10 넣어주기

 

기본적으로 반복문을 자릿수만큼 반복을 해가며 1, 0을 더해주면 분해합을 구하기 끝!

 

STEP 3 분해합이 입력받은 값과 같은지 판별

if(sum == num) {
	   	 			sum = i;
	   	 			break;
	   	 			}
	   	 		
	   	 		sum = 0;
	   	 		digit = 0;

이 문장은 뭐... 아주 간단해서 말해드릴 게 없습니다.... 최솟값을 구하기는 하지만 i는 1부터 작은 수대로 판별하기 때문에 가장 먼저 if문에 걸린 게 정답이 될 수밖에 없지요

 

또한 sum에 i를 넣어주는 것은 바로 sum을 출력하기 위해서입니다.

 

아래에 있는 sum, digit을 0으로 초기화하는 이유는 또 i 변수의 반복문이 반복하려면 해당 값들에 들어있는 이전 값들을 초기화해주어야 되기 때문이죠!

 

---

해당 STEP을 따라와 보시면 의외로 정말 간단한 문제임을 알 수 있습니다. 분해합에서 가장 중요한 점은 바로 자릿수를 어떻게 판별할 것인지 라고 생각합니다.