[BOJ] 2231번: 분해합

https://www.acmicpc.net/problem/2231

2231번: 분해합

 

Python3

if __name__ == '__main__':
    num = int(input())
    has_num = False
    for i in range(1, num, 1):
        dst_sum = i
        dst_num = i
        while dst_num >= 10:
            dst_sum += dst_num % 10
            dst_num //= 10
        dst_sum += dst_num
        if dst_sum == num:
            print(i)
            has_num = True
            break
    if not has_num:
        print(0)

처음엔 브루트포스 알고리즘을 사용하지 않고 해결할 수 있는 방식이 있나 고민했지만 해당 방식을 쓰지 않고 각 자리 수의 조합을 찾기란 불가능에 가까웠다. 분해합은 생성자와 생성자의 각 자리수의 합이기 때문에 항상 분해합 > 생성자 일 수 밖에 없다. 따라서 브루트포스 방식으로 1이하 분해합 미만의 수들을 모두 보면서 분해합을 구했을 때 주어진 분해합과 일치하는 생성자를 골랐다. 생성자가 여러개 존재할 수 있고 그 중 제일 작은 생성자를 고르라고 했으므로 이 문제는 단순히 1부터 분해합을 만들 수 있는지 보면 됐다. 

분해합을 구하기 위해서는 각 자리의 수를 알아야 했는데 이는 10으로 나눈 나머지로 구할 수 있었다. 이렇게 해서 구한 분해합이 주어진 분해합과 일치한다면 해당 생성자를 출력했다.

생성자가 존재하지 않는 상황에는 0을 출력하라고 했으므로 has_num이라는 조건 변수를 추가하여 생성자가 존재하는지를 판별했다. 없을 경우 0을 출력했다.

 

처음엔 문제를 잘못읽고 생성자의 분해합을 구한다는 것으로 문제를 이해했다. 너무 쉬운데,,? 하고 풀고나서 아닌 것을 알았다... 역시 문제를 잘 읽자!