[백준/C++] 2231번 분해합

문제: www.acmicpc.net/problem/2231

2231번: 분해합

 

문제풀이

 

모든 경우의 수를 비교하는 브루트 포스 문제이다.

 

입력값 N의 최소 생성자를 찾아내야 하는데

나는 1부터 N까지의 수 모두 N의 생성자가 될 수 있는지 여부를 확인해보는 코드를 작성했다.

 

N % 10 과 N /= 10 연산을 이용해 분해합의 필요한 각 자릿수의 덧셈을 하였다.

 

코드

#include <iostream>

using namespace std;

int main(){
    ios::sync_with_stdio(false); cin.tie(NULL);

    int N;
    cin>>N;
    
    for(int i=1; i<N; i++){
        int sum = i;
        int part = i;
        while(part){ //더이상 나눌수 없으면 while문 종료
            sum += part%10; //자릿수 덧셈
            part /= 10; //다음 자릿수로 넘어가기
        }
        if(sum == N){ //만일 N의 생성자가 맞다면
            cout<<i; //출력
            return 0;
        }
    }

    cout<<0; //생성자가 존재하지 않는다면 0 출력

    return 0;
}

 

결과

 

문제를 풀고 다른 사람의 코드를 보았을 때

검사해야 하는 숫자의 범위를 확연하게 줄일 수 있는 방법이 있어 놀랐습니다.

입력값 N의 자릿수를 확인한 뒤 자릿수 곱하기 9를 N에서 뺀 숫자부터 검사를 실행하면 됩니다.

이때 자릿수에 9를 곱하는 이유는 각 자릿수는 아무리 커봐야 9이기 때문입니다.

 

N - (N의 자릿수)*9 <= (검사범위) < N

 

예를 들어 N이 354, 세 자릿수의 숫자일 때 검사해야 하는 숫자의 범위는

 

354 - 3*9 = 327

 

327 <= (검사범위) < 353 입니다.