백준 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을 출력한다.

 

---

정답풀이

#분해합
N = int(input())

result = 0
for i in range(1,N+1):
    A = list(map(int,str(i)))
    result = i + sum(A)
    if(result == N):
        print(i)
        break
    #체크했는데 값이 없는 경우
    elif i == N:
        print(0)

 

Q) for i in range(1,N+1) 이라는 반복문은 굳이 왜 사용한 것일까?

A) 문제의 '가장 작은'의 조건을 맞추기 위해 1부터 체크하는 반복문을 사용한 것. 중복으로 값이 나오는 것을 방지하기 위해 break로 값이 나오면 반복문을 나갑니다.

 

Q)elif i == N: 이라는 조건은 왜 있는건지?

A) i == N 이라는 것은 반복문으로 모든 경우를 체크하였다는 것입니다. 자리수 + 값 = 값일 수는 없으니, i == N 인 경우가 마지막인 것이 맞습니다. 따라서 모든 경우를 체크하였지만 값이 없는 경우이고 따라서 0을 출력합니다.

 

 

오답풀이

 

주석과 같은 아이디어로 자리수를 나눠 구하려고 하였으나, 코드가 너무 길어지고 방향이 잘못되었음.

#분해합

flag = 0
def check_constructor(N):
    global flag
    max_digit = N
    #1,000,000 백만이 최대이므로 생성자는 최대 5자리수
    #중복이 가능해야 하므로 -> 배열을 활용

    #생성자의 최대 자리수 구하기
    e = 1
    while max_digit >= 10:
      e += 1
      max_digit = max_digit//10
    
    #자리수 e-1부터 e까지만 체크하면 됨
    #ex) 108 = 99 + 9 + 9 ,  1026 = 999 + 9 + 9 + 9, ... 더해봤자 한자리 이상 넘어갈수 없기 때문

    ##case1 1<= N < 100

    #case1)-1 홀수인 경우
    #1의 자리수의 홀수는 작은 생성자가 없음
    if(N<10 and N%2 == 1):
        print(0)
        flag = 1
        return
    elif(10<=N<100 and N%2 == 1):
        for i in range(1,9+1):
            for j in range(0,9+1):
                if(11*i + 2*j == N):
                    print(10*i+j)  
                    flag = 1
                    return         
    #case1)-2 짝수인 경우
    # 18까지는 그냥 2로 나누면 됨    
    elif(N<=18 and N%2 == 0):
        print(N//2)
        flag = 1
        return
    elif(18<N<100 and N%2 == 0):
        for i in range(1,9+1):
            for j in range(0,9+1):
                if(11*i + 2*j == N):
                    print(10*i+j) 
                    flag = 1
                    return
                    

    

    ##case2 100<= N < 1000
    #case2)-1 생성자가 2자리 수 인 경우 99 + 9 + 9 = 117이므로 최대 117의 값을 가진다.
    elif(100<=N<=117):
        for i in range(1,9+1):
            for j in range(0,9+1):
                if(11*i + 2*j == N):
                    print(10*i+j) 
                    flag = 1
                    return
    #case2)-2 생성자가 3자리 수 인 경우
    elif(118<=N<1000):
        for i in range(1,9+1):
            for j in range(0,9+1):
                for k in range(0,9+1):
                    if(101*i+11*j+2*k == N):
                        print(100*i+10*j+k)
                        flag = 1
                        return

    #case3 1,000<= N < 10,000
    # elif()




    
        
N = int(input())

check_constructor(N)
if flag == 0:
    print(0)
# #자리수 2개
# print(N//10,N%10)
# #자리수 3개
# print(N//10//10,N//10%10, N%10)
# #자리수 4개
# print(N//10//10//10,N//10//10%10, N//10%10,N%10)
# #자리수 5개
# print(N//10//10//10//10,N//10//10//10%10, N//10//10%10,N//10%10,N%10)

 

 

답안 풀이와의 다른점 및 배울점

1. 자바나 C를 사용하면서 자리수를 구할 때 몫과 나머지를 활용하였으나, 파이썬에서는 map 을 통해 자리수를 바로 구할 수 있다.

 

2. 가장 작은 -> for 문을 돌리는 경우가 많다. 

 

3.case분류도 정도가 있지 5개~6개가 넘어가는 경우면 방향이 잘못되었는지 다시 생각해볼 필요도 있다.

(나는 이번 풀이에서 10 100 1000 10000 100000 100000로 분류하였지만, 분기가 너무 많다고 의심해보지 못했다.)

 

4.자리수를 구하기 위해 % /를 사용하면 되었는데 for문을 여러번 돌릴 생각을 했는데, 이렇게 풀면 안된다. 

(주석 보면 분명히 몫과 나머지를 통한 idea로 구하려고 했는데 왜 나는 자리수마다 중복 for문을 돌리려고 하였는가.. 미리 설계해둔 코드로 비지니스 로직을 해야한다)

*최대한 있는 변수를 사용하자

 elif(18<N<100 and N%2 == 0):
        for i in range(1,9+1):
            for j in range(0,9+1):
                if(11*i + 2*j == N):
                    print(10*i+j) 
                    flag = 1
                    return
                    
                    
         VS
                    
                    
result = 0
for i in range(1,N+1):
    A = list(map(int,str(i)))
    result = i + sum(A)
    if(result == N):