[BF] 2331번 분해합

2231번 분해합

 

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

 

문제

어떤 자연수 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을 출력한다.

 

예제 입력

216

 

예제 출력

198

 

해결방법

모든 경우를 다 해보는 간단한 완전탐색 문제이다

 

• N의 조건은 N ≤ 1,000,000
• 자연수 n 이 주어졌을 때, 생성자는 반드시 n 보다 작음
• 생성자 중, 가장 작은 생성자 출력

 

이러한 조건을 바탕으로 생각해볼 수 있는 것은 그냥 1,000,000번 다해보면 되는거 아닌가...?? 이다

1부터 n-1 까지 반복문을 돌리며 분해합 조건이 맞다면 출력하고 프로그램을 종료하면 해결된다

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <algorithm>
#define MAX 1000000
#define INF 987654321
using namespace std;

int n;

bool solve(int num){
    string d = to_string(num);
    int sum = num;
    
    for(int i=0; i<d.size(); i++){
        sum += (d[i]-'0');
    }
    
    if(sum == n){
        return true;
    }
    
    return false;
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    
    for(int i=1; i<n; i++){
        if(solve(i)){
            cout << i << "\n";
            exit(0);
        }
    }
    cout << 0 << "\n";
    
    return 0;
}