[백준] #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

백준 2231번 문제

💡Idea

X의 각 자릿수의 합 + X = N

N의 생성자인 X는 위의 식을 통해서 찾을 수 있기 때문에 아래의 두 조건을 부합해야 합니다.

1. X는 N보다 작다.

   ▶ X의 각 자릿수의 합은 0보다 크기 때문

2. X는 N에서 X의 각 자릿수의 합의 최댓값을 뺀 값보다 크다.

   ▶ X의 각 자릿수의 합의 최댓값을 뺀 값보다 작으면, 절대 X를 더해서 N이 될 수 없기 때문

따라서, N - 각 자릿수의 합의 최댓값 ~ N-1의 범위에서 X를 찾지 못하면, N을 생성하는 생성자 X는 존재하지 않는다고 할 수 있습니다.

각 자릿수의 합의 최댓값은 N의 자릿수 * 9입니다.

예를 들어, N이 세자릿수라면 일의 자릿수, 십의 자릿수, 백의 자릿수가 최대로 가질 수 있는 값은 모두 9입니다.
따라서 각 자릿수들의 합이 가질 수 있는 최댓값은 3 * 9 = 27입니다.

💻코드1

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

answer = 0
for i in range(N - (9 * (N.bit_length() // 3)), N): #1
    decomposition_sum = i 
    temp = i # 확인하려는 수 그대로 시작
    while temp > 0: # 확인하려는 수 i의 뒷자릿수부터 더해나감
        decomposition_sum += temp % 10 # 나머지가 되는 일의 자릿수의 값을 더함 
        temp = temp // 10 # temp의 자릿수를 하나 줄임
    if decomposition_sum == N: # 분해합이 N이라면 종료 
        answer = i
        break

print(answer)

📝코드 설명1

위에서 찾은 범위 내의 수들의 분해합을 계산해보며, N과 동일한 값을 가지는지 확인합니다.

분해합을 계산하는 과정은 다음과 같습니다.

1. 확인하려는 수의 뒷자리부터 더해나갑니다.
2. 확인하려는 수를 10으로 나눈 나머지는 일의 자릿수가 됩니다.
   EX) 215 % 10 = 5(215의 일의 자릿수)
3. 구한 일의 자릿수를 더합니다.
4. 확인하려는 수를 10으로 나눈 몫(소수점은 잘라버린)은 이미 더한 일의 자릿수를 뺀 나머지 수가 됩니다.
   EX) 215 // 10 = 21(이미 더한 5를 제외한 수)
5. 새로 만들어진 4번의 수를 가지고 2번으로 되돌아가 수의 모든 자릿수를 더할 때까지 위의 과정을 반복합니다.

변수

• N : 주어진 자연수
• decomposition_sum : 현재 확인하고 있는 수의 분해합을 저장하는 변수
• temp : 현재 확인하고 있는 수의 각 자릿수들을 뽑아내기 위한 임의의 변수

#1 : N - N이 가질 수 있는 각 자릿수의 최대합 ~ N-1까지의 수를 확인하면서 분해합이 N이 되는 수가 있는지를 확인합니다.
이 때 가장 작은 생성자를 구해야 하므로, 가장 작은 값부터 시작하여 1씩 큰 값을 확인해나갑니다.

💻코드2

사실 아래와 같이 1부터 N-1까지의 수들의 분해합을 모두 계산해보아도 시간 초과가 일어나지 않습니다.

👇 for문의 범위만 다른 코드

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

answer = 0
for i in range(1, N): # 1부터 N-1까지 반복
    decomposition_sum = i
    temp = i
    while temp > 0:
        decomposition_sum += temp % 10
        temp = temp // 10
    if decomposition_sum == N:
        answer = i
        break

print(answer)

⏰시간복잡도 비교

1. 1부터 N-1까지의 범위로 생성자 구하기

• 메모리 : 30840 KB
• 시간 : 1416 ms

2. N - X의 각 자릿수의 최대 합 ~ N까지의 범위를 좁혀 생성자 구하기

• 메모리 : 30840 KB
• 시간 : 76 ms

👉시간이 거의 20배 정도 차이가 나는 것을 확인하실 수 있습니다.