[백준 / BOJ] - 2231번 분해합 C++ 풀이

---

 

백준 - 단계별로 풀어보기 [2231] 

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

문제

 

 

245의 분해합은 245+2+4+5 = 256일때, 245는 256의 생성자라고 정의한다.

어떤 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하는 문제이다.

 

풀이

 

1부터의 분해합을 구해서 최초로 N과 같은 수가 나오면 출력해주면 되는 문제이다.

이 때, 1부터의 분해합을 모두 구하면 비효율적이므로 조금이나마 연산횟수를 줄일 수 있도록 시작점을 구하는 코드를 추가했다.

 

N이 3자리 숫자일경우, 최소값인 100을 만족하는 숫자는 86이다. 

 

따라서 시작점을 N이 i자리 수일때, 10^(i-1) - 9 * (i-1)로 시작하도록 하였다.

N의 값이 커질수록 불필요한 연산의 수를 크게 줄일 수 있다.

 

 

코드

 

#include <iostream>
#include <cmath>
using namespace std;

void numfind(int N)
{
    int tmp = N;
    int start,i,sum,tmp2 = 0;
    for(i = -1; tmp; i++)
        tmp /= 10;
    start = round(pow(10,i)) - 9*i;
    tmp = start;
    while(1)
    {
        sum = tmp;
        tmp2 = tmp;
        while(tmp2)
        {
            sum += tmp2 % 10;
            tmp2 /= 10;
        }
        if(sum == N)
        {
            cout << tmp;
            return;
        }
        if(tmp == N)
        {
            cout << '0';
            return;
        }
        tmp++;
    }
}
int main() {
    int N;
    cin >> N;
    numfind(N);
}

 

 

평가

 

Brute Force 문제는 단순히 모든 경우의수를 고려해주면 되므로,

문제의 코딩 난이도가 어렵지는 않다.