객체지향 프로그래밍을 해봤다면 지문 이해가 쉬웠을 것 같습니다.
어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라고 합니다.
간단히 말하자면 M으로 인해 N이 생겨났으니, 주체인 M이 N의 생성자라고 생각하면 됩니다.
그랬을 때 문제에서 N이 입력으로 주어지면 우리는 M을 구해야 합니다.
그중에서도 가장 작은 M을 구하려면 M을 1부터 검사하면서 N을 만들 수 있는 생성자를 찾아가면 됩니다.
언제까지 찾으면 될까요?
확실한 건 M은 N보다 클 수 없습니다. 생성자니까요.
따라서 N보다 작을 때까지만 루프를 돌면 됩니다.
calc함수는 어떤 자연수의 각 숫자의 합을 리턴하는 함수입니다.
문자열로 쪼개서 계산해도 되지만, 이러한 방식이 오히려 더 편할 수 있습니다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int calc(int n)
{
int sum = 0;
while(n)
{
sum += n % 10;
n /= 10;
}
return sum;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int cur = 1;
bool found = false;
while(cur < n)
{
int num = cur + calc(cur);
if(num == n)
{
cout << cur << endl;
found = true;
break;
}
cur++;
}
if(found == false)
cout << "0\n";
return 0;
}
'Algorithm' 카테고리의 다른 글
[백준 11051] 이항 계수 2 (0) | 2022.01.11 |
---|---|
[백준 1654] 랜선 자르기 (0) | 2021.12.23 |
[백준 1991] 트리 순회 (0) | 2021.12.12 |
[백준 1120] 문자열 (0) | 2021.12.09 |
[백준 2960] 에라토스테네스의 체 (0) | 2021.12.07 |