백준 - [단계별로 풀어보기 브루트 포스] 2231 분해합

이번 문제는 분해합으로 브루트포스 알고리즘에 관한 문제이다. 문제에서 말하는 분해합이란 어떤 수와 그 수의 각 자리수의 합을 더한 값을 의미한다. 예를 들어 어떤 수가 198이라면 분해합은 다음과 같이 계산된다.

198 + 1 + 9 + 8 = 216

 

이 경우 198은 216의 생성자가 된다. 문제에서는 입력으로 주어진 수 N에 대해 분해합이 N이 되는 가장 작은 생성자를 찾는 것이 목표이다.

처음에는 입력된 값에서 자리수를 빼는 방식으로 생성자를 역으로 찾을 수 있을 것이라 생각했다.

예를 들어 216이라는 값이 주어졌다면 다음과 같이 계산할 수 있을 것이라 생각했다.

216 - 2 - 1 - 6

 

하지만 이렇게 계산하는 방식은 항상 올바른 결과를 보장하지 않는다. 실제로 입력값을 기준으로 역으로 계산해 보았을 때 출력값과 일치하지 않는 207이라는 값이 도출되었다. 알아보니 이는 생성자의 자리수와 결과값의 자리수가 항상 동일하지 않기 때문이었다.

또한 문제 설명에는 생성자가 여러 개인 자연수도 존재할 수 있다는 내용이 포함되어 있었다. 따라서 이 문제는 특정 공식을 이용하기보다는 가능한 모든 경우를 확인하는 브루트포스 방식으로 접근하는 것이 가장 간단한 해결 방법이다.

0부터 N까지 모든 수를 검사하면서 다음과 같은 과정을 반복한다.

1. 현재 숫자를 하나 선택한다.
2. 해당 숫자의 각 자리수를 분해하여 합을 구한다.
3. 숫자와 자리수의 합을 더한 값이 N과 같은지 확인한다.
4. 같다면 해당 숫자는 N의 생성자가 된다.

이 과정에서 처음 발견되는 생성자가 가장 작은 생성자이기 때문에 바로 결과를 출력하면 된다.

만약 끝까지 생성자를 찾지 못한다면 0을 출력한다.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp3
{
    internal class BruteForce
    {
        static void Main(string[] args)
        {
            // 2231 분해합
            int N = int.Parse(Console.ReadLine());

            // 0부터 N까지 하나씩 검사하면서 생성자가 있는지 확인
            for (int i = 0; i < N; i++)
            {
                int sum = i;   // 분해합 계산을 위해 시작값을 i로 설정 (i + 자리수합)
                int temp = i;  // 자리수 분해를 위해 사용할 임시 변수

                // temp의 각 자리수를 하나씩 꺼내기
                while (temp > 0)
                {
                    sum += temp % 10;  // 현재 자리수 추가
                    temp /= 10;        // 다음 자리수로 이동
                }

                // 계산한 분해합이 N과 같다면 i는 N의 생성자
                if (sum == N)
                {
                    Console.WriteLine(i); // 가장 먼저 발견된 생성자 출력
                    return;               // 프로그램 종료 (최소 생성자이므로 더 찾을 필요 없음)
                }
            }

            // 끝까지 찾지 못했다면 생성자가 없는 것
            Console.WriteLine(0);
        }
    }
}

이 문제를 풀기 위해 분해합에 대한 내용에 매몰되어 생성자를 역으로 계산하려고 접근했지만, 생성자의 자리수와 결과값의 자리수가 항상 동일하지 않기 때문에 단순한 역연산으로 해결할 수 없다는 것을 알게 되었다. 결국 0부터 N까지 모든 숫자를 확인하며 숫자 + 자리수의 합을 계산하는 방식으로 문제를 해결할 수 있었다.