백준 2231 분해합

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

Problem

자연수 N의 가장 작은 생성자 x를 구하라

• 245의 분해합은 245 + 2 + 4 + 5 = 256
• 245는 256의 생성자

Input
자연수 N(1 ≤ N ≤ 1,000,000)

Output
가장 작은 생성자 x
생성자가 없는 경우 0

Plan

1. 자릿수 찾기
   99, 999, 9999,...의 분해합 과 비교하며 자릿수 찾기
2. 첫번째 자릿수 찾기
   만약 1번에서 세자릿수로 결정됐다면, 199, 299, 399,...로 증가시키면서 첫 번째 자릿수 찾기
3. 두번째 자릿수 찾기
4. 없으면 1로 돌아감