백준 문제들을 풀며 답을 정리하는 글입니다.

2231 - 분해합 [브루트포스]

출처 : 백준_2231_분해합

문제

숫자가 입력으로 주어지면 해당 숫자의 가장 작은 생성자를 구하는 것이 문제이다.

숫자 자신과 각 자릿수들에 해당하는 숫자들을 더했을 때 어떤 숫자가 나온다면, 더해지기 전 숫자가 더해진 숫자의 생성자가 되는 것이다. 예를 들어, 245를 자기 자신과 각 자릿수들을 더하면 다음과 같다: 245+2+4+5 = 256. 256의 생성자는 245가 되는 것이다.

이러한 특성을 지니는 생성자를 찾아야 한다.

풀이

브루트 포스이기 때문에 0부터 주어진 숫자까지 loop을 돌면서 생성자를 찾으려고 했다.

예를 들어,

• 0 -> 0+0 = 0 …
• 10 -> 10+1+0 = 11 …
• 111 -> 111+1+1+1 = 114 …

그러고 생성자를 발견했으면 그 숫자가 가장 작은 생성자이기 때문에 loop를 빠져 나오게 했다.
만약, 어떤 숫자가 주어졌을 때 최소한 어떤 숫자보다는 커야 생성자가 만들어질 수 있을 것 같은 조건을 찾게 되면 이 시간은 더 줄어들 것으로 보인다. 물론, 브루트포스 방법이기 때문에 이런 것을 고려하지 않고 그냥 구현했다….