2231 분해합

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

2231번: 분해합

분해합 성공

한국어   

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

192 MB

18689

9583

7930

50.664%

문제

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.

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

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.

 

<풀이>

1. 문제 조건을 보면, 생성자 숫자의 최소값을 찾는 문제이다.

 이 최솟값은 자연수 1부터 N의 최대 범위 백만 까지 탐색을 진행하며 시간 복잡도는 O(N)이다

 

2. 탐색을 오름차순으로 진행하며 처음 발견된 생성자가 결국 최솟값이 될 수 있다는 것을 알 수 있다.

 

3. 나머지는 그냥 기초구현

 

#include<string>
#include<iostream>

using namespace std;

int ans = 1000000;
int N;
int check(int n, string &str);
int main(void)
{
	cin >> N;
	string str;

	for (int i = 1; i <= N; ++i)
	{
		str = to_string(i);
		if (check(i, str))
		{
			if (ans > i)
				ans = i;
			cout << ans << '\n';
			break;
		}
	}
	if (ans == -1)
		cout << 0 << '\n';
	return 0;
}
int check(int n, string &str)
{
	int temp = 0;
	for (int i = 0; i < str.length(); ++i)
	{
		temp += str[i] - '0';
	}
	
	int val = temp + n;
	if (val == N)
	{
		ans = val;
		return 1;
	}
	else ans = -1;
	return 0;
}