Tags :

• 문제
• 풀이
• 새로 배운 것들

문제

백준 2231 - 분해합

어떤 자연수 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을 출력한다.

풀이

#include <iostream>
using namespace std;

int main ()
{
   int N = 0;
	int answer = 0;
	cin >> N;

	for (int i = 0; i < N; ++i)
	{
		int n = i;
		int sum = 0;
		while (n > 0)
		{
			sum = sum + n % 10;
			n = n / 10;
		}
		answer = i + sum;
		if (answer == N)
		{
			cout << i;
			return 0;   // 여기서 break;로 썼다가 아래 cout << 0;까지 출력되면서 틀렸다!
		}
	}
	cout << 0;

    return 0;
}

새로 배운 것들

• 브루트포스(Brute-force search) : 모든 경우의 수를 확인하는 알고리즘
  브루트포스, 키 전수조사 또는 무차별 대입은 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 암호를 해독하는 방법이다. 흔히 암호학에서 연구되나, 다른 알고리즘 분야에서도 사용되고 있다.
  
  

• 나머지 연산으로 자릿수 더하기 계산법

        int n = i;
        int sum = 0;
        while (n > 0)
        {
            sum = sum + n % 10;
            n = n / 10;
        }
  

  while문을 통해 숫자가 0이되기 전 까지 (int라서 1 이하 소숫점 0.1 = 0으로 연산) 10으로 나눠주고 나머지 자릿수를 반복해서 더해주는 방식을 배웠다
  if문으로 10의자리수, 100의자리수 하나하나 계산하려했던 내자신이 하찮다…
  좀 더 익숙해지자