[코딩테스트/백준/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을 출력한다.

💡생각

1. N을 입력받는다.
2. 삼중 for문을 이용해 3개의 숫자(i, j, k)를 뽑아낸다.
3. if문을 활용해 int(i+j+k)+int(i)+int(j)+int(k)==N인 i,j,k를 알아내 result에 저장한다.
4. result를 출력한다.
5. result의 값이 0이면 0을 출력한다.

❓잘못된 코드1

반례를 못찾음.

문제점1. 3자리숫자까지만 정확한 답변이 나오고 숫자가 커지면 0을 출력함.

N = int(input())

def main(N):
    result = 0
    resultarr = []

    for i in range(0,10):
        for j in range(0,10):
            for k in range(0,10):
                if int(str(i)+str(j)+str(k)) + i + j + k == N:
                    resultarr.append(int(str(i)+str(j)+str(k)))

    if not resultarr:
        print(0)
    else:
        result = min(resultarr)
        print(result)
    
main(N)

❗해결: 10^6자리수까지 고려해야함.

💡테스트 통과한 코드

N = int(input())
    
def main(N):
    result = 0

    for i in range(0, 1000000):
        if (i + (i//10**5) + (i%10**5//10**4) + (i%10**4//10**3) + (i%10**3//10**2) + (i%10**2//10) + (i%10)) == N:
            result = i
            print(result)
            break

    if result == 0:
        print(result)
                 
main(N)

⏬다른사람의 코드

---

내가 나눠서 자릿수를 더해준 것보다 다른 사람의 코드에서 map함수를 이용해서 자릿수를 더해주는 것이 더 효율적인 코드인 듯.

target = int(input())
min_target = abs(target - (len(str(target)) * 9))
 
for i in range(min_target, target):
    temp = sum(map(int, str(i)))
    result = i + temp
    if result == target:
        print(i)
        break
else:
    print(0)

🔗풀이 참고
https://ywtechit.tistory.com/110

---

✅sum 함수

• sum(iterable)은 인자로 전달되는 iterable의 합을 리턴.
  아래 예제에서 sum(list)는 list의 합을 리턴.

list = [10, 22, 19, 2, 9, 3]
sum_list = sum(list)

print(sum_list)

# 65

• sum(iterable, start)
  sum(iterable)은 인자로 전달되는 iterable의 합과 start를 더한 값을 리턴.

list = [10, 22, 19, 2, 9, 3]
sum_list = sum(list, 1000)

print(sum_list)

# 1065

🔗참고
https://codechacha.com/ko/python-sum/#sumiterable-start

🔗백준 - 분해합
https://www.acmicpc.net/problem/2231