[BOJ][2231] 분해합

문제

문제 출처

문제 해결 전략

주어진 N에서 부터 인덱스를 하니씩 줄여가면서 생성자가 되는 것들만 vector에 저장한 후에 마지막에 vector중에서 최소를 출력해주기만 하면된다.
선형 탐색을 이용하지만 N/2보다 작은 값은 절대 생성자가 될 수 없기 때문에 중간까지만 탐색하게 만든다.

코드

#include<string>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
	int N; cin >> N;
	string sn ="";
	int sum = 0;
	vector<int> ans;
	int flag = 0;
	for(int i = N;i >= N/2;i--){
		sum = 0;
		sn = to_string(i);
		for(int j = 0;j < sn.length();j++){
			sum += sn[j]-'0';
		}
		if(sum + i == N){
			ans.push_back(i);
			flag = 1;
		}
	}
	if(flag == 1) cout << *min_element(ans.begin(), ans.end()) << endl;
	else cout << "0\n";

}