[C++] 백준 2231 분해합

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

2231번: 분해합

 

 

1. 서론

 

브루트 포스 분류의 문제다. 사실 알고리즘 유형을 잘 몰라서 브루트 포스 유형의 문제라고 하면 그게 어떤 문제인지 감이 오지 않았는데 브루트 포스는 한 마디로 무식하게 a~z로 다 돌려서 노가다 하는 것이라고 한다. 알고 보니 내가 맨날 하던 그 짓이 '브루트 포스'였음... ㅋ

 

2. 문제 풀이

 

어떤 자연수 n이 있다. 그리고 그 n을 분해해서 더한 분해합 m이 있다. 예를 들어서 n이 245이면 m은 245 + 2 + 4 + 5, 즉 256이 된다.

분해합 m이 주어졌을 때 자연수 n을 구하는 것이 문제이다. 처음에는 좀 당황했다. 어떻게 m만 가지고 n을 유추하는 식을 만들 수 있을까 숫자의 조합을 고민하다가 그냥 한 번 무식하게 다 해보자는 생각이 들었다. m부터 0까지 역순으로 돌리면서 값을 계산해 분해합이 나오는 n값을 하나하나 다 계산해서 구했다. 생성자가 여러 개인 경우에 가장 작은 것을 출력하라는 조건을 보고 이렇게 풀어야겠다고 생각했다.

왜냐하면 역순으로 돌리니까 어차피 제일 작은 수가 변수에 남을 것 같아서...

근데 확신은 없고 (식을 구해서 코드를 짜는 문제일까봐...) 그냥 한 번 해보자 했는데 맞았다...

 

3. 코드 설명

 

#include <iostream>

using namespace std;

int main()
{
    int i, x, m, n = 0, t = 0;

    cin >> m;

    for (i = m; i >= 0; i--)
    {
        t += i;
        x = i;
        while(x > 0)
        {
            t += x % 10;
            x /= 10;
        }

        if (t == m) n = i;
        t = 0;
    }

    cout << n << endl;
}

 

m을 입력받고 m에서 0까지 돌리면서 자연수 n을 구한다. 

변수 t에 i값을 저장하고 i값을 일의 자리 단위로 쪼개서 t에 더해준다. 그러면 분해합이 구해지는데 이 값 t가 m과 같으면 n에 그 값을 저장해준다. m에서 0 순으로 점점 값이 작아지기 때문에 가장 작은 n값으로 저장된다.

n이 안 구해지는 경우에는 0을 출력해야 하기 때문에 n값을 0으로 초기화해준다.