2231 문제 분해합 풀이
생성자 M이 N을 만들수 있다. N이 주어질경우 M을 찾아라
하지만 주어진건 N이기때문에 이를 딱히 찾을 방도가 없다.
그렇기 때문에 이문제는 무차별 대입으로 풀어야한다.
여기서 빅오를 줄일 방법이 존재하는데 M은 N보다 작다는 점이다.
왜냐하면 M은 N의 분해합을 하기때문에 작을수가 없다.
소스는 다음과 같다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int fn(int n) {
auto str = std::to_string(n);
for (int i = 0; i<str.size(); i++)
n =n+(str[i]–‘0’);
return n;
}
int main() {
int n;
cin >> n;
int result = 0;
for (int i = 1; i < n; ++i) {
if (n == fn(i)) {
result = i;
break;
}
}
std::cout << result << std::endl;
}
|
cs |