백준) 분해합

문제) https://www.acmicpc.net/problem/2231

 

어느새 백준 단계 12 브루트 포스 카테고리에 있는 문제를 풀기를 시작하였다. 브루트 포스 알고리즘은 다른거 설명 필요없이 완전 탐색을 하는 알고리즘으로 노가다성 문제이다.

 

그 중 오늘은 문제를 보다가 문제 설명만 듣고 바로 코드를 작성하지 못하는 문제를 포스팅을 하기로 했다.

 

해당 문제에서 요구하는 답은 N을 주어 졌을 때 가장 작은 생성자를 찾는 문제이다.

 

여기서 순간 헷갈리게 되었다. 생성자? 그게 뭐지 하면서 문제를 처음 부터 차근히 읽어 본 결과 245의 분해의 합이 256(245 + 2 + 4 + 5)이 되어 245가 256의 생성자가 된다고 한다.

 

여기서 쉽게 말하여 본인의 수에 각 자리의 수를 더해서 나온 수가 있으면 생성자가 되는 문제이다.

 

예시가 적어 헷갈릴 수 있으니 여러개의 예시를 들어보자

분해합	분해식	생성자
13	11 + 1 + 1	11
129	123 + 1 + 2 + 3	123
1244	1234 + 1 + 2 + 3 + 4	1234

 

이렇게 예시를 만들게 되면 어는 순간 아 생성자가를 어떻게 찾는 감이 오기 시작 한다.

 

그런데 문제에서 주어진 것은 가장 작은 생성자이다. 즉 N보자 작은 모든 수 찾아 분해식을 돌려야 하는 문제 인것이다.

 

정답 코드

import sys
N = int(sys.stdin.readline().strip())
k = N - 1
p_list = []
while k > 0:
    k_list = list(str(k))
    check_sum = 0
    for i in k_list:
        check_sum += int(i)

    if check_sum + k == N:
        p_list.append(k)
    k -= 1

if len(p_list) > 0:
    print(min(p_list))
else:
    print(0)

 

코드를 보면 쉽게 알 수 있듯이 생각 보다 코드는 쉽게 작성이 가능하다. 그런데 여기서의 문제를 읽고 이해 하기까지가 시간이 걸렸었다.

 

그래도 어떻게 해결 할 수 있게 다행인 문제이나 해당 문제는 다음에 다시 한번 풀어 봐야 할 듯하다.