브루트포스 - 백준 2231번 분해합

www.acmicpc.net/problem/2231

2231번: 분해합

IDEA 

맨 처음에는 ABC라는 숫자면 분해합이 ABC + A + B + C 즉 2C + 11B + 101A 라는 점에서 어떤 수식을 도출할 수 있을 줄 알았는데 곰곰히 생각해보면 어림도 없을 거 같다. 

 

1부터 주어진 숫자까지 하나하나 분해합을 구해서 비교하는 방식을 생각해보았는데, 

어차피 가장 큰 수인  1,000,000이 들어와도 1초에 1억번이니까 충분히 연산을 할 수 있을 거라고 생각해서 그냥 무식하게 for문을 돌리는 방법을 선택했다. 이런 걸 브루트포스라고 하나보다. 

 

1. 1부터 주어진 숫자 n까지 for문을 통해 하나하나 탐색한다. 

2. i라는 수에 대해서 while문을 통해 계속 10으로 나누면서 자릿수 + i 즉, 분해합을 구해준다. 

3. 분해합과 내가 찾는 n이 같은지 확인한다. 

 

코드 C++ 

#include <iostream>
using namespace std;

int main() {
	int n;
	scanf("%d", &n);
	bool check = false;
	for (int i = 0; i < n; i++) {
		int num = i;
		int sum = num;
		while (num > 0) {
			sum += num % 10;
			num /= 10;
		}
		if (sum == n) {
			printf("%d", i);
			check = true;
			break;
		}
	}
	if (!check) printf("0");
}