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;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
알고리즘 200일 프로젝트 - 5day
내일도 열심히!
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 6603번: 로또 (0) | 2020.04.12 |
|---|---|
| 백준 7568번: 덩치 (0) | 2020.04.11 |
| 백준 14502번: 연구소 (0) | 2020.04.11 |
| 백준 14501번: 퇴사 (0) | 2020.04.10 |
| 백준 2309번: 일곱 난쟁이 (0) | 2020.04.10 |