백준 2231 - 분해합(JAVA)

9/15일에 study원들과 코테 스터디를 진행하고 뽑아 본 5개의 문제 중 하나를 풀어 보았다. 

 

2231번: 분해합 (acmicpc.net)

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을 출력한다.

예제 입력 1

216

예제 출력 1

198

 

분해합 문제이다. 처음 문제를 볼 때 1학년 당시 했던 자릿 수 합을 생각했는데, 생성자라는 새로운 개념을 가지고 접근 하는 문제였다. 생성자로 분해합을 출력시키는 문제였다면 월등히 쉬웠을 거 같은데 분해합을 가지고 생성자를 구하는 문제이다 보니 생각보다 자꾸 헷갈려서 시간이 조금 소요된 듯 하다.

 

알고리즘은 간단하다.

 

어떤 숫자 N을 입력받는데 그 숫자가 분해합이다. 그 분해합을 만들 수 있는 최소의 생성자를 출력시키면 된다.

 

1. 반복문으로 1~N까지의 수를 모두 조사한다.(브루트 포스법)

2. 정해진 수를 가지고 숫자를 쪼개는 것이 아니다 보니 객관성이 있게 while문 안에서 반복적인 작업을 해주어야 한다.

3. 찾은 생성자의 분해합이 입력받은 수와 동일해 지면 그 수를 출력시키면서 반복문 종료

4. 생성자가 없는 경우는 반복문을 돌리지 않고 그냥 0 출력

 

 나는 이렇게 해결을 했다. 

 

num : 생성자 변수

sum : 분해합 변수

 

sum에 처음 부터 체크할 생성자 수 i를 담아 두면 sum 변수에 자릿수를 더하기만 하면 변수를 하나 줄이고 쉽게 해결 할 수 있다. 처음엔 변수를 두 개나 더 만들었었는데, 오히려 너무 헷갈려서 정신이 없어져 그냥 처음부터 값을 넣어서 시작하는 방법을 택했다.

 

이렇게 오늘도 한 문제 해결 끝!!!