[Python 파이썬] 백준 2231번 - 분해합

2024년 6월 26일

문제 링크 :  백준 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을 출력한다.

 

알고리즘 분류

• 브루트포스 알고리즘

---

 

문제 접근

 

245의 분해합은 245 + 2 + 4 + 5 = 256 이다.

이 때, 256의 생성자는 245이다.

 

어떤 수 N이 주어졌을 때, 가장 작은 생성자를 구하는 문제이다.

생성자는 여러 개 일 수 있기에 가장 작은 생성자를 구해야 하며, 없다면 0을 출력한다.

 

N을 보고 어떠한 규칙을 찾아 생성자를 찾는 것은 불가능하기에 1부터 N까지 모든 수의 분해합을 구해 가장 먼저 분해합이 N인 수를 출력하는 방식으로 로직을 구성해야 한다.

이 방식이 가능한 이유는 N이 최대 1,000,000이고 시간 제한이 2초이기 때문이다.

 

1 ~ N까지 모든 수의 분해합이 N이 되는 경우가 존재하지 않는다면, 0을 출력한다.

 

N + 1부터는 분해합이 절대 N이 될 수 없기 때문에 N까지만 완전 탐색을 진행한다.

---

입력 예제

 

216

 

 

 

출력 예제

 

198

 

 

---

전체 코드

 

# 2231

N = int(input())

now = 0
while True:
    if now > N:
        print(0)
        break

    sum = now
    str_now = str(now)
    for idx in range(len(str_now)):
        sum += int(str_now[idx])
    
    if sum == N:
        print(now)
        break
    

    now += 1

 

 

---

풀이 후기

 

브루트포스 방식으로 완전 탐색을 할 수 있는 간단한 문제였다.