[SWEA] (C++) D4 7854 최약수

IO가 좋게 주어져 있어서 어렵진 않은 문제였다.

일단 먼저 생각해볼게 최약수를 구하는 방법은 다음 자릿수가 현재의 수로 나누어 지면 된다.

예를 들어, 현재 수가 12345라 가정하면 100000가 12345로 나눠진다면 이 앞에 어떠한 수가 와도 나눌 수 있다.

다시 말하면 10 ^ (현재 자릿수 - 1) % 현재 수 == 0이면 최약수인데, 이러한 수는 1, 2, 5, 25, 125 가 있다.

이 뒤에 0이 붙는 수도 최약수다. ex) 10, 100, 200, 1250, ... 등등

이러한 방식을 알면 쉽게 풀 수 있는 문제다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(int argc, char** argv)
{
	vector<int> DIVIDE;

	for (int temp = 0, i = 1; temp <= 9; temp++, i *= 10)
		DIVIDE.push_back(i);
	for (int temp = 0, i = 2; temp < 9; temp++, i *= 10)
		DIVIDE.push_back(i);
	for (int temp = 0, i = 5; temp < 9; temp++, i *= 10)
		DIVIDE.push_back(i);
	for (int temp = 1, i = 25; temp < 9; temp++, i *= 10)
		DIVIDE.push_back(i);
	for (int temp = 2, i = 125; temp < 9; temp++, i *= 10)
		DIVIDE.push_back(i);

	sort(DIVIDE.begin(), DIVIDE.end());

	int test_case;
	int T;

	cin >> T;

	for (test_case = 1; test_case <= T; ++test_case)
	{
		int X; cin >> X;

		int cnt = 0;
		for (int i = 0; i < DIVIDE.size(); i++)
			if (X >= DIVIDE[i])
				cnt++;

		cout << '#' << test_case << ' ' << cnt << '\n';
	}
	return 0;
}