분해합 백준 2231번 c++

문제

분해합 백준 2231번

리뷰

N의 생성자를 찾으려면 1부터 N-1 까지 전부 탐색하면 된다.

N은 1이상 100만 이하의 수가 들어오니까 for문으로 찾아도 2초 시간제한을 초과하지 않는다.

각 자리의 수가 가질 수 있는 최대 숫자는 9이다.

 

N이 219 일 때, 219는 3 자리수이다.

219에서 9를 3번 빼면 219의 생성자의 최소값을 구할 수 있다. 219 - 9 -9 -9 = 192

따라서 192 부터 218까지 탐색해서 생성자를 구해도 된다. 1부터 탐색할 필요가 없다.

맞은 코드 1

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

int N, answer;

int Sum_total(int n){ 

    int sum = n; // 일단 자기 자신을 더한다. 
    while(n > 0){ 
        sum += (n%10);  // 각 자리수를 더한다 
        n /= 10;
    }
    return sum;
}

int main(void){

    cin >> N;

    for(int i = 1; i < N; i++){

        int sum = Sum_total(i);

        if(sum == N) {
            answer = i;  // 생성자 찾음 
            break;
        }
    }    

    printf("%d", answer);  

    return 0;
} 

맞은 코드 2

#include <iostream>
#include <cmath>
#include <algorithm> 
#include <functional>
using namespace std;

int N, answer; // 생성자 못찾으면 answer = 0

int main(void){

    cin >> N;

    int tempN = N;
    int len = 0;

    while(tempN > 0){ // 1. N의 자리수 len에 구하기  
        tempN /= 10;
        len++;
    }

    int start_n = len*9; // 자리수 만큼 9를 뺸다 

    for(int i = start_n; i < N; i++){

        int sum = i;
        int temp = i;

        while(temp > 0){ // 2. 각 수의 자리수의 합  
            sum += (temp%10);
            temp /= 10;
        }

        if(sum == N) {
            answer = i; // 생성자 찾음 
            break;
        }
    }    

    printf("%d", answer);

    return 0;
}