[백준] 2231번 분해합 (C)

출처

ICPC Asia Regional Seoul 2005 B번

문제 주소

백준 2231번 분해합

힌트

모든 경우를 다 확인해도 제한 시간 안에 가능하다.

 

 

풀이

제한시간이 2초이고 입력받는 n의 범위가 1,000,000이하이다. 이는 O(n)풀이가 가능하다는 말이다. 따라서 1부터 n까지 확인하여 분해합이 n과 같다면 그 수를 출력하면 된다.

#include<iostream>
using namespace std;

int main(){
    int n;
    cin>>n;

    for(int i=1;i<=n;i++){
        int sum=i,tmp=i;

        for(int j=10000000;j>=1;j/=10){
            sum+=tmp/j;
            tmp%=j;
        }

        if(sum==n){
            cout<<i;
            return 0;
        }
    }
    cout<<"0";
}

백준 2231번 분해합