BOJ 2231번 : 분해합

손풀기용 브론즈 문제!!

딱 문제 보자마자 느껴지는 브루트포스.

최대 자연수가 1,000,000 이므로 생성자의 최대 자리수는 6자리 이고, 각 자리는 0부터 9까지 10개 이므로, 6중 for문을 사용한다 해도 시간복잡도는 10^6 이므로, 시간제한에 훨씬 못미친다. 즉, 6중 for문을 사용하는것이 제일 간편하다.

 

생성자의 각 자리수를 a~f까지 설정하고 모든 경우의 분해합을 확인하고, 없을경우 0을 출력하면 끝!

 

<소스코드>

#include<iostream>
using namespace std;

void Solve(int n) {
	int _tem = 0;
	for (int a = 0; a < 10 && _tem==0 ; a++) {
		for (int b = 0; b < 10 && _tem == 0; b++) {
			for (int c = 0; c < 10 && _tem == 0; c++) {
				for (int d = 0; d < 10 && _tem == 0; d++) {
					for (int e = 0; e < 10 && _tem == 0; e++) {
						for (int f = 0; f < 10 && _tem == 0; f++) {
							_tem = (100000 * a + 10000 * b + 1000 * c + 100 * d + 10 * e + f) + a + b + c + d + e + f;
							if (_tem == n) {
								cout << _tem - (a + b + c + d + e + f);
								break;
							}
							else
								_tem = 0;
						}
					}
				}
			}
		}
	}

	if (_tem == 0)
		cout << _tem;
}

int main() {
	int n;
	cin >> n;
	Solve(n);
	return 0;
}

 

<문제>

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

2231번: 분해합