백준 2231번: 분해합

 

 

---

1~N까지 완전탐색을 돌려도 시간 제한에 걸리지 않는 문제지만 생성자의 한가지 규칙을 발견하여 적용시켰다.

각 자리수는 0~9의 값만 가지기 때문에 각 자리수의 합은 최대 9 * N을 넘지 못한다.

ex) 99->9+9=18, 999->9+9+9=27

분해합 = 생성자+자리수이므로 생성자의 최솟값은 (분해합 - (9*N)) 인 것을 알 수 있다. 

---

#include <iostream>
using namespace std;
 
int Solution(int num)
{
    int temp = num;
    int cnt = 1;
    while ((temp /= 10) != 0)
        cnt++;
    int start = num - (cnt * 9);
    for (int i = start; i < num; i++)
    {
        temp = i;
        int sum = temp;
        while (temp / 10 != 0)
        {
            sum += temp % 10;
            temp /= 10;
        }
        sum += temp;
        if (sum == num)
        {
            return i;
        }
    }
    return 0;
}
int main(void)
{
    int num;
    cin >> num;
    cout << Solution(num) << endl;
 
    return 0;
}
 

 

 

 

알고리즘 200일 프로젝트 - 5day

내일도 열심히!