[백준 2231] 분해합

🛎 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

 

🔎 문제분석

어떤 수 N의 분해합을 구하는 거라면 쉬웠을 텐데, 분해합의 가장 작은 생성자(=곧, 어떤 수 N)를 찾는 문제라 난해했다.

- 이 문제는 분해합과 생성자의 관계를 파악하려 하면 더 힘들었다.    * 왜냐하면 생성자->분해합은 값이 하나로 떨어지지만   * 분해합->생성자를 구하는 건 결과값이 여러 개일 수 있기 때문이다. - 여기저기 알아보다보니 어차피 O(N) 속도라면, 1부터 1000000까지 돌리면서 분해합이 N인 경우를 찾기도 한 걸 봤는데,   아무리 O(N)이라지만, 백만개를 다 돌리는 건 비효율적일 것 같아 다른 방법을 찾아보았다

 

(1) N의 생성자의 최대값은 N - 1이다.

주어진 분해합 값 N의 범위는 (1 ≤ N ≤ 1,000,000) 

==> 그렇다면 N의 생성자의 자릿수는 최대 6개 곧, 999,999가 된다. (생성자는 분해합 보다 적어도 1만큼 적을 것)

 

(2) N의 생성자의 최소치는 N - 54이다.

* M = N의 생성자

N = M + (M의 각 자리수에 대한 합)

==> M의 각 자릿수의 최대치는 999,999이다.

==> N = 999,999 + (9 * 6)

==> (M의 각 자리수에 대한 합)의 최대치는 (9 * 6)이다.

==> M의 최소치는 곧, 54

N - (9 * 6) = M

 

(3) (1)~(2)를 종합해보았을 때, N의 생성자의 범위는 

N - 54 <= M <= N - 1

 

⌨️ 코드