[C언어] 백준 2231 : 분해합

백준 2231 : 분해합

 

문제 링크

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

2231번: 분해합

 

 

문제 내용

(요약) 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자릿수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다.

자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구하는 프로그램을 작성하라.

ex) 245의 분해합은 256(=245+2+4+5). 즉 245은 256의 생성자

 

 

Idea

N의 생성자를 찾기 위해 1부터 N까지 하나하나 찾아보면 찾을 수 있는 문제이긴 하지만 찾고자 하는 범위를 줄여 불필요한 계산은 피하고자한다.

 

분해합은 자기 자신과 각 자릿수의 합으로 이뤄지므로

최소 (자기 자신) - 9*(자릿수)이다.

 

9를 곱해주는 이유는 각 자릿수에서 가장 큰 수가 9이기 때문이다.

단, 수가 일의 자리거나 십의 자리일 경우 최소구간을 정할 때 음수가 되므로 0으로 바꿔준다.

 

 

Code

#include <stdio.h>
 
int main() {
    int N, tmp, digit = 0, generator = 0;
    scanf("%d", &N);
    tmp = N;
 
    //자릿수 구하기
    while (tmp > 0) {
        tmp /= 10;
        digit++;
    }
 
    //최소범위 구하기
    tmp = N;
    tmp = tmp - digit * 9;
    if (tmp < 0) tmp = 0;
 
    //생성자 찾기
    int num, sum = 0;
    for (int i = tmp; i <= N; i++) {
        num = i;
        //현재 수 더하기
        sum += num;
        //각 자릿수 더하기
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
 
        //생성자를 찾으면 저장하고 break
        if (sum == N) {
            generator = i;
            break;
        }
        sum = 0;
    }
    //결과출력
    printf("%d\n", generator);
    return 0;
}