본문 바로가기
코딩과 알고리즘

백준 2231. 분해합 문제 풀이

백준 2231. 분해합 문제 풀이

"분해합"이라는 수학용어가 있습니다.
어떤 자연수 N을 N과 각 자릿수를 1의 자리로 하여 합산한 수를 분해합이라고 하는데요.

이를테면 123 이란 숫자의 분해합은 123 + 1 + 2 + 3 = 129가 됩니다.
이 때 반대로 123을 129의 생성자라고 합니다.

이번 문제는 129 입장에서 123과 같은 생성자를 구하는건데요.
주어지는 숫자는 최대 1,000,000까지 가장 작은 생성자를 구하는 겁니다.

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

 

2231번: 분해합

문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다. 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그

www.acmicpc.net

그냥 1부터 시작해서 주어지는 숫자까지 모든 경우의 수를 계산하다 첫번째 나오는 숫자를 구하면 되지 않나 할 수 있지만 2초의 시간제한이 있습니다.

사실 C++같은 경우 속도가 빨라서 2초 안에 대부분 구해지긴 할겁니다.
하지만 시간적으로 훨씬 효율적인 방법이 있습니다.

우선 주어지는 숫자가 123,456 이라고 쳐봅시다.

분해합은 생성자와 각 자릿수를 모두 더한 숫자인데,
각 자릿수를 모두 더한 수는 그렇게 큰 수가 아닙니다.

그러니까 123,456은 6자리 숫자이기 때문에
각 자릿수는 가장 커봐야 9 + 9 + 9 + 9 + 9 + 9 일겁니다.
즉 9 x 6자리 = 54라는 것이지요.
그렇다면 생성자는 123,456 - 54 보다 항상 크거나 같을 수 밖에 없습니다.
결국 123,402 부터 123,456 중에서만 생성자를 찾으면 되는 것이지요.

그럼 풀이 원리로 알아볼까요? 소스 해설보다는 알고리즘 설명입니다 :)

1번째. 먼저 주어지는 숫자의 자릿수를 구해야 합니다. 정수일 경우 해당하는 방법입니다.
숫자의 자릿수를 구하려면 해당 숫자를 10으로 반복해서 나눠주면서 몇번 나누면 0이 되는지를 구합니다.

123,456 의 경우 6번 10으로 나눠주면 되므로 6자리입니다.
123456(시작), 12345(1), 1234(2), 123(3), 12(4), 1(5), 0(6)

2번째. 검사를 시작할 수치를 구합니다. 자릿수에 따라 상이합니다.
256의 경우 3자리이므로  3에 각 1의 자릿수가 가질수 있는 최대값 9를 곱하면 3 x 9 = 27 가 되므로 검사를 시작할 수치는 229 가 됩니다.

3번째. 검사를 시작할 수치부터 주어진 수치까지 반복하면서 분해합이 주어진 수치와 동일한지 비교합니다.
첫번째 발견한 수치에서 중지합니다.
256의 경우 시작 수치 229 ~ 256 까지 검사합니다.

각 자릿수의 합계를 구하는 방법은 여러가지가 있지만
C++ 에서는 sprintf 명령문으로 문자열에 수치를 기록한 다음,
각 자리마다 수치를 더해주는 기법을 사용할 수 있어 속도가 매우 빠릅니다.

4번쨰. 3번째에서 조건에 맞는 수치를 발견했다면 해당 수치를 출력하고 종료합니다.
하지만 발견하지 못했다면 0을 출력하고 종료합니다.


위 알고리즘대로 반영된 소스입니다.
백준 사이트에서 돌려보면 소요시간이 0 ms 입니다 :)

#include <iostream>
#include <cstring>

using namespace std;

int main() {

	long n;
    std::cin >> n;
    // 숫자자릿수부터 계산
    long m = n;
    int digit = 0;
    while (m)
    {
        m /= 10;
        digit++;
    }
    // 분해합은 최소 n - 9*n의 자릿수 부터 시작
    long begin = n - digit * 9;
    char s[10];
    long sum = 0;
	bool find=false;
    for (long i = begin; i <= n; ++i)
    {
        sprintf(s, "%ld", i);
        sum = i;
		for(int j=0;j<strlen(s);++j)
			sum += s[j]-'0';
        if(sum == n )
		{
			find=true;
			cout << i << "\n";
			break;
		}
    }
	if(find==false)	cout << "0\n";

	return 0;
}

 

 

 

 

 

 

  • BlogIcon 버블프라이스 2019.10.03 07:50 신고

    오늘은 백준 2231- 분해합 문제 풀이를 해주셧군요?
    포스트 잘 읽고 갑니다.
    개천절 공휴일 입니다. 의미있는 날 보내시길 바래요-^^

  • 질문 2020.01.01 20:09

    저는 8ms 가 나왔습니다.
    아래 내용을 적당히 보시면 이해하실 텐데요. 저도 크레이폴님 처럼 answer의 범위를 좁혔는데 저는 왜 8ms가 나올까요?
    그리고 시작 범위를 설정할 수 있다는 아이디어는 혁명입니다 :)

    cin >> N;
    int temp = 0;
    temp += N / 10;
    temp += N / 100;
    temp += N / 1000;
    temp += N / 100000;
    temp += N / 10000;
    temp += N / 1000000;
    answer = N - temp;
    while (answer <= 1000000) {
    int newNum = 0;
    int cri = answer;
    newNum += cri;
    while (cri != 0) {
    newNum += (cri % 10);
    cri /= 10;
    }
    if (newNum == N) {
    break;
    }
    answer++;
    }

    //delete part
    if (answer == 1000001)
    cout << 0 << "\n";
    else
    cout << answer << "\n";

  • 질문 2020.01.01 20:26

    틀린 부분이 있었습니다... 그 수의 내용을 바로 빼는군요 ㅎㅎ

  • 질문 2020.01.01 20:30

    cin >> N;

    answer > N - 54 ? N - 54 : N;// 그냥 54를 빼는 것으로 고쳤더니 8ms가 나옵니다!

    while (answer <= 1000000) {
    int newNum = 0;
    int cri = answer;
    newNum += cri;
    while (cri != 0) {
    newNum += (cri % 10);
    cri /= 10;
    }
    if (newNum == N) {
    break;
    }
    answer++;
    }

    //delete part
    if (answer == 1000001)
    cout << 0 << "\n";
    else
    cout << answer << "\n";

  • tjs 2020.09.19 21:56

    만약 n에 3이 들어가면 탐색을 -6부터 시작할 듯 한데, 그러면 s[0]이 '-'이 되고 '-' - '0' = 45-48 = -3이니 예외처리를 잘 해야겠네요.