취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 6605번 문제인 Humble Numbers이다.
문제는 아래 링크를 확인하자.

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

입력으로 주어지는 n의 값이 5842까지이므로, 탐색해야하는 수의 대상이 굉장히 적다는 것을 알 수 있다.

2, 3, 5 및 7의 지수를 0부터 하나씩 늘려나가면서 가능한 조합들을 찾아 문제를 해결하자.

예제로부터 5842째 수가 20억을 넘지 않는 것을 확인할 수 있으므로, 이를 이용해 탈출조건을 설정하면 반복문을 이용한 브루트포스로 20억 이하의 humble number들을 모두 찾아낼 수 있다.

서수를 표기할 때, n의 일의 자리가 1이면 st, 2이면 nd, 3이면 rd를 붙여줘야 한다. 단, n이 11, 12 또는 13으로 끝난다면 th를 붙여줘야한다. (eleventh, twelfth, thirteenth)

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

vector<ll> vec;
string ordinal[100];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 0; i < 100; i++) ordinal[i] = "th";
	for (int i = 1; i < 100; i += 10) ordinal[i] = "st";
	for (int i = 2; i < 100; i += 10) ordinal[i] = "nd";
	for (int i = 3; i < 100; i += 10) ordinal[i] = "rd";
	ordinal[11] = ordinal[12] = ordinal[13] = "th";

	ll val2 = 1;
	while (val2 < 2000000001) {
		ll val3 = val2;
		while (val3 < 2000000001) {
			ll val5 = val3;
			while (val5 < 2000000001) {
				ll val7 = val5;
				while (val7 < 2000000001) {
					vec.emplace_back(val7);
					val7 *= 7;
				}
				val5 *= 5;
			}
			val3 *= 3;
		}
		val2 *= 2;
	}

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

	int x; cin >> x;
	while (x) {
		cout << "The " << x << ordinal[x % 100] << " humble number is " << vec[x - 1] << ".\n";
		cin >> x;
	}
}