백준알고리즘 2231번 분해수 C#

세부 정보

• 사이트: 백준알고리즘
• 번호: 2231
• 문제명: 분해수
• 언어: C#
• 분류: 브루트포스 알고리즘
• 비고: 

 

문제

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

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

 

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

 

출력

첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.

 

풀이

풀이를 작성하세요.

// 분해합 구하는 과정
int DecompostionSum(int n)
{
    // 반환할 분해합
    int sum = n;
    while (true)
    {
        // 0을 입력한 경우 해당 함수에서 빠져나온다
        if (n == 0) break;

        // 입력한 수를 10으로 나눈 나머지를 계속 더한다
        sum += n % 10;
        // 입력한 수를 10으로 나눈 몫울 다시 넣는다.
        n /= 10;
    }

    return sum;
}

// 자연수를 입력받아 저장
int n = Convert.ToInt32(Console.ReadLine());

for (int i = 1; i < n; i++)
{
    if(DecompostionSum(i) == n)
    {
        Console.WriteLine(i);
        return;
    }
}

Console.WriteLine(0);

 

후기

브루트포스 알고리즘을 처음 풀어보았다. 사실 문제 풀어보기 전에 브루트포스 알고리즘이 가능한 모든 경우의 수를 대입해 문제를 해결하는 것은 알고 있었다. 그래서 도전을 해 보았다.

StreamReader sr = new StreamReader(Console.OpenStandardInput());
StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());


int n = Convert.ToInt32(sr.ReadLine());
int con = 1000000;

if(n < 10)
    sw.WriteLine("0");

if(n >= 10)
{
    for (int i = 10; i <= n; i++)
    {
        int wholeNum = i;
        string separateNum = Convert.ToString(i);

        for (int j = 0; j < separateNum.Length; j++)
        {
            wholeNum += Convert.ToInt32(separateNum[j]);
        }

        if (con > wholeNum)
            con = wholeNum;
    }
    sw.WriteLine(con);
}

sr.Close();
sw.Close();

 

하지만 위 스크립트에 10 이상인 어떤 수를 입력해도 결과는 107로 고정되어서 나왔다. 왜 저런 값이 나왔는 지 추적해보기 위해 디버깅을 해 봤지만 지역 변수에 접근할 수 없어서 왜 고정된 값이 나왔는 지 파악할 수 없었다. 전역 변수는 잘만 되는데 지역 변수는 어떻게 해야 하는 지 조사해 보기로 하겠다.

역시나 자릿수를 나누는 함수를 만드는 것이 상식이었다. 함수를 만드는 형태로 프로그램을 짜보는 것을 연습해 보기로 하면서 풀이를 마친다.