[백준 알고리즘] 2231번: 분해합 (파이썬 / Python)

문제

어떤 자연수 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

---

 

문제 접근

문제의 조건은 가장 작은 생성자를 찾고, 생성자가 없는 경우의 출력도 존재한다.

비교를 위해 특정 변수(result라고 하자.)를 생성, 생성자이고 최솟값이라면 해당값을 result에 넣게끔 하면 될 것 같다.

 

수정 전 정답 코드(느림)

import sys
n = int(sys.stdin.readline())

result = n

for i in range(1, n+1):
    sum = 0
    for j in range(len(str(i))):
        sum += int(str(i)[j])       #i를 자릿수마다 나누어 더해주는 부분
    if sum + i == n and i < result: #i가 생성자이고 최솟값이라면
        result = i                  #결과값에 할당

if result == n:                     #결과값이 처음과 똑같다면 (생성자가 없는 것임)
     print(0)
else: print(result)

 

처음 제출한 코드이다. 설명은 다음과 같다.

• 1부터 n까지 탐색하고 인덱스 i를 string으로 형변환
• 각 자리의 합 + i = n 을 통해 생성자 구별
• result에 n을 할당
• 첫 생성자 발견 시 해당 값 result에 할당 (추가 발견 시에는 더 작은 값이 아니라면 할당 X)
• for문 종료 후, result가 n이라면 생성자가 발견되지 않은 것이므로 0을 출력, 아니라면 result를 출력

 

잘 작동되었지만, 채점했을 때 속도가 느려 다른 공개 답을 참고하여 수정하였다.

 

수정 후 정답 코드(빠름)

import sys
n = int(sys.stdin.readline())
                                   #추가코드
min = n - (len(str(n))*9)          #n의 생성자가 될 수 있는 최솟값
if min <= 0:                       #이 최솟값이 음수가 된 경우 1로 초기화
    min = 1

result = n

for i in range(min, n+1):
    sum = 0
    for j in range(len(str(i))):
        sum += int(str(i)[j])       #i를 자릿수마다 나누어 더해주는 부분
    if sum + i == n and i < result: #i가 생성자이고 최솟값이라면
        result = i                  #결과값에 할당

if result == n:                     #결과값이 처음과 똑같다면 (생성자가 없는 것임)
     print(0)
else: print(result)

 

4~6 라인을 추가하였다.

N의 생성자가 될 수 있는 최솟값은 N - (N의 자릿수 * 9) 라고 한다.

해당 값을 for문 탐색 range의 시작값에 넣어 시간을 엄청나게 줄일 수 있었다.

 

아래가 수정 전, 위가 수정 후이다. 무려 50배의 차이가 난다.

아주 약간의 변화를 주는 것이 프로그램에 큰 영향을 줄 수 있다는 점을 배웠다.

 

 

 

 

2231번: 분해합