백준 2231 - python

1. 문제

https://www.acmicpc.net/problem/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을 출력한다.

예제입력

알고리즘 분류

브루트포스 알고리즘

2. 나의 생각

분해합을 구하는 것이 아니라 생산자를 구하는 문제,
어떻게 보면 거꾸로의 값을 구하는 것이라 생각되어 뇌가 멈췄다.

입력값 안에서 값을 정하고 그 값을 빼서 나머지를 한자리 수로 세개 나눠서 더했을 때 같게 하면 될까..?

이렇게 어렵고도 어리석은 생각을 했다.

결국 구글링의 도움을 받아 해결했다.

또한 수의 각 자리수 합을 for문이 아니라 간단하게 구하는 방법도 배울 수 있었다!

3. 풀이

N = int(input())

ans = 0

for i in range(1, N+1):
    A = sum(map(int, str(i)))
    ans = A + i
    if ans == N:
        print(i)
        break
    if i == N:
        print(0)

1. 자연수 N을 입력받는다.
2. 생산자는 자연수 보다 작으므로 자연수 안에서 반복시킨다.
3. "입력값(N) = 생산자 + 생산자의 각자리 수 합" 이므로
4. 생산자는 1부터 N까지 고려된다.
5. A는 생산자의 각 자리수 합으로 map(int, str(i))
6. 그렇게 i값이 N값을 끝으로 증가하면서 입력값과 같은 순간이 오면
7. i 값이 생산자가 되고 반복문을 멈춘다.
8. 그러나 i가 입력값 N이 될 때 까지 생산자가 나오지 않았다면, 생산자가 없는 자연수 이므로 0을 출력한다.