[BaekJoon] 백준 2231 분해합 (Python / 파이썬)

BaekJoon 백준 BOJ 2231 분해합 문제는 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자릿수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 할 때 생성자를 구하는 문제이다. 난이도는 Bronze 2이다.

 

BaekJoon 2231 분해합 문제 정보

출처

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

알고리즘 분류

- 브루트 포스 알고리즘 (brute force algorithm)

난이도

- 브론즈 2 / Bronze 2

 

분해합 문제 요약

• 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자릿수의 합을 의미한다.
• 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다.
• 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다.
• 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.
• 자연수 N(1 ≤ N ≤ 1,000,000)이 주어졌을 때, N의 가장 작은 생성자를 구하여 출력한다.
• 생성자가 없는 경우에는 0을 출력한다.

 

문제 풀이 과정

1. 생성자는 N보다 작으므로 M에 N을 초기 값으로 저장해 놓는다.
2. 생성자를 1부터 N까지 모두 탐색하여도 시간 초과가 나지 않지만, 시간을 절약하기 위해 탐색 범위를 줄이자.
3. 생성자를 탐색할 범위의 시작 수는 생성자 후보가 될 수 있는 최소 수인 N - 9X(자연수 N의 자릿수)이다.
4. 그런데 N - 9X(자연수 N의 자릿수)가 0보다 작으면 그냥 0부터 N까지 모두 탐색한다.
5. 가장 작은 생성자를 구해야 하므로 생성자를 하나라도 찾으면 탐색을 중단한다.
6. 생성자를 출력한다.

 

코드 및 설명

• ans - 생성자
• start - 생성자를 탐색할 범위의 시작 수

N = int(input())
ans = 0
start = max(N - 9 * len(str(N)), 0)
for i in range(start, N):
    if N == sum(map(int, str(i))) + i:
        ans = i
        break
print(ans)

---

BaekJoon 백준 BOJ 2231 분해합 문제를 파이썬 python으로 풀어보았다. 브루트 포스 알고리즘 활용 문제로 난이도는 Bronze 브론즈 2이다.