BOJ 2231 분해합

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미하고, 어떤 자연수 M의 분해합이 N이면 M을 N의 생성자라고 한다.
예를 들어, 245의 분해합은 245+2+4+5=256이 되고, 245가 256의 생성자가 된다. 자연수마다 생성자가 없을 수도 있고, 여러개 있을 수도 있는데, 이 문제는 입력으로 어떤 자연수가 주어지면 그 자연수의 생성자 중 최소값을 구하는 문제이다. (생성자가 없다면 0 출력)

일단 N 제한은 100만이다. 그리고 어떤 자연수 n의 생성자는 n이하일 수 밖에 없다. 일단 최소값을 구하는 문제이므로 1부터 n까지 다 해보면서 구하면 될 것 같다.

구현해 봐야겠다. AC를 받았다.
다른 분들 풀이를 보니까 n이 70보다 클 경우 1부터 보지않고, n-70부터 보는데, 생각해보니 최대 100만이므로 7자리 수인데, 분해할 경우 한 자리의 최대값은 9이다. 그래서 더해질 수 있는 합의 최대값을 대략 10*7로 하신 것 같고 70보다 큰 값이 들어오면 70이전부터만 보는 것 같다. 좀 더 정확히는 9*6만 해도 될 것 같다. 100만이 최고이므로 그 이전 수들은 6자리 수이므로... 한 번 9*6으로 해서 제출해 봐야겠다. AC를 받았다. 100만번 돌던 것을 70번밖에 안도니 확실히 시간이 확 줄어든다.