[BaekJoon] 2231번 : 분해합 (Python)

코딩 1일 1문제! 오늘의 문제는 백준의 분해합 입니다.

2231번: 분해합

👨🏻‍💻 문제 풀이

이 문제는 어떤 숫자를 입력 받았을 때

해당 숫자에 생성자가 있다고 하면 생성자를 생성자가 없으면 0을 정답으로 하는 문제입니다.

생성자가 있는 숫자란 무엇인가!

생성자가 있는 숫자 = 숫자 + 숫자의 각 자리 수

34의 경우 
26 + 2 + 6 == 34 이므로
34의 생성자는 26이 됩니다.

이 문제는 셀프넘버 처럼 풀 수 있지만 처음부터 탐색하게 되면 비효율적입니다.

 

그래서! 탐색하는 범위를 줄였습니다.

어떤 숫자 N 이 주어지면 생성자가 될 수 있는 최대의 수 만큼을 뺀 다음 탐색을 시작했습니다.

min_num = N - (len(str(N)) - 1) * 9 - int(str(N)[0])

입력 받은 숫자의 길이만큼 9 를 더한 값 + 입력 받은 숫자의 맨 앞자리 숫자 만큼을 뺀 값을 

탐색의 시작 숫자로 두었습니다.

 

그 다음은

answer = 0

for num in range(min_num, N):
    temp = num + sum(list(map(int, list(str(num)))))

    if temp == N:
        answer = num
        break

셀프넘버를 찾는 방식으로 문제를 풀었습니다.

 

전체 코드는 아래를 참고해주세요.

👨🏻‍💻 코드 ( Solution )

def decomposition_sum(N):
    answer = 0
    N_len = len(str(N))
    
    min_num = N - (len(str(N)) - 1) * 9 - int(str(N)[0])
    
    for num in range(min_num, N):
        temp = num + sum(list(map(int, list(str(num)))))
        
        if temp == N:
            answer = num
            break
            
    return answer

if __name__ == "__main__":
    N = int(input())
    print(decomposition_sum(N))

GitHub - SOMJANG/CODINGTEST_PRACTICE: 1일 1문제 since 2020.02.07