BOJ 2231번 : 분해합

안녕하세요. 지난 포스팅의 BOJ 2798번 : 블랙잭에서는 브루트포스 알고리즘에 대한 간단한 설명과 함께 문제를 파이썬의 itertools 클래스를 이용해서 문제를 풀어보았습니다. 오늘도 브루트포스와 관련된 문제를 풀어보도록 하죠. 

 

 

완벽한 코딩은 존재하지 않습니다. 제가 제출한 코드 역시 마찬가지고 그저 참고만 해주시길 바랍니다. 

 

핵심 포인트

• 브루트포스

 

제출 코드

N = int(input())

flag = 0
for i in range(1, 1000001) :
    temp = i
    sum = temp
    while temp != 0 :
        sum += temp % 10
        temp //= 10
    if sum == N : 
        flag = 1
        print(i)
        break
if flag == 0 : print(0)

 

해설

이 문제는 이해만 한다면 아주 쉽게 풀 수 있는 문제입니다. 일단, 문제에서 말하길 입력되는 숫자에는 여러 개의 생성자가 존재하고 생성자란 숫자와 각 자리 숫자의 합으로 새로운 숫자를 만들었을 때 입력되는 숫자와 같게 되는 경우를 말한다고 하였습니다. 어떤 자연수는 생성자가 존재하지 않기도 하죠. 그리고 입력되는 숫자의 범위는 최대 1,000,000까지 이군요. 이번에도 시간이 조금 소요되더라도 브루트포스를 이용해서 전수탐색을 해보도록 하겠습니다. 

 

먼저, 1 ~ 1,000,000 까지의 숫자를 하나씩 보면서 분해합을 계산해줍니다. 각 자리 숫자의 합을 계산하는 방법은 지금까지 저희가 많이 해왔기 때문에 아주 쉽게 할 수 있을 겁니다. 다음으로 입력된 숫자와 분해합 결과와 같아면 해당 숫자를 바로 출력해주면 됩니다. 왜냐하면 가장 작은 생성자만 출력하면 되기 때문이죠. 그런데, 생성자가 없는 경우도 있죠. 이 경우에는 flag 변수를 이용해서 조절해주면 됩니다. 위 코드에서 만약, 생성자가 존재한다면 flag 변수의 값이 0에서 1로 바뀌게 됩니다. 하지만, 1,000,000까지 조사했는데 존재하지 않는다면 flag = 0 이고 이 경우에는 입력되는 숫자의 생성자가 없다는 뜻이므로 그대로 0을 출력해주면 되죠.

 

참고자료 및 그림출처

백준 코딩 문제