백준 2231번 C/C++

이 문제가 조금 글이 이상하게 적혀있어서 이해를 못해서 블로그 글을 찾는 사람이 많을 것 같아서

먼저 이렇게 문제 이해를 도와드리겠습니다.

acmicpc.net/problem/2231

[

2231번: 분해합

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이

www.acmicpc.net

](http://acmicpc.net/problem/2231)

예시에서 245의 분해합이 256이라고 한다. 245 + 2 + 5 + 6이라서 256이다.

이 256을 분해합으로 가지는 가장 작은 수를 구하라는 것이 이 문제의 물음이다.

참고로 256을 입력으로 입력을 하면 245가 나온다.

글이 이해가 안되서.. 처음에는 분해합을 구하는 줄 알았다가 전혀 아닌거 같아서 다시 자세히 하나하나 읽어보니 알게 되었다.

그리고 이 문제 풀이에 대한 힌트를 드리겠습니다.

힌트? 인지는 정확하게 모르겠지만 백준을 풀면서 하도 시간 초과가 많이 나와서 항상 반복문의 수를 줄이거나 범위는 줄이는 생각을 많이 하였습니다.

여기서 범위를 줄이는 방법은 (분해합 수) - 9*(총자리수)입니다. 만약 위처럼 256을 분해합을 가지는 수를 구할 때 범위는 256-9*3<= 범위 <= 256 => 229<= 범위 <=256입니다.

그 이유는 3자리일 때 가장 큰 수는 999입니다. 그렇기에 9*(총자리수)를 빼면 범위가 나옵니다.

이러한 힌트를 가지고 코딩을 진행하면 이제 그 뒤는 쉽게 풀 수 있습니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

int main()
{
    int n;
    scanf("%d", &n);        //n이 246일때 분해합은 246 + 2 + 4+ 6 = 258이다. 수를 입력 받음.
                            //이때 246은   258의 생성자이다.
    int count = 0; int m = n;       //n과 m은 같다.
    while (n != 0) {
        count++;            //자리수 카운트 -> 범위를 알기 위해서
        n = n / 10;
    }

    int checkCount = 0; // sum == m이 있는지 확인하는 변수
    int sum = 0; int i;
    for (i = m - 9 * count; i <= m; i++) {
        int j = i;
        sum = j;
        while (j != 0) {
            sum = sum + j % 10;
            j = j / 10;
        }

        if (sum == m) {
            checkCount++;
            break;
        }
    }

    if (checkCount != 0) {
        printf("%d", i);
    }
    else {
        printf("0");
    }
 
}