취미로 코딩하기

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

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

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

주어지는 각 정수가 문제에서 요구하는 두 조건을 만족하는지를 확인하는 문제이다.

양의 정수 N이 K 이하의 수로 나누어지는지의 여부는 N이 K보다 작거나 같은지, 그리고 N이 \(min(K, \sqrt{N})\) 이하의 소수로 나누어지는지의 여부를 이용해 판단할 수 있다. 에라토스테네스의 체를 이용해 가능한 소수의 후보들을 미리 구해두고 문제를 해결하자.

같은 숫자가 네번 이상 연속으로 나오는지는 to_string을 이용해 주어진 수를 문자열로 가공해 판단하면 간단히 구현할 수 있다.

문제의 조건에 따라 1은 항상 조건을 만족시킴에 유의하자.

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

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

ll N, K;
bool sieve[100000];
vector<ll> primes;

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

	sieve[0] = sieve[1] = 1;
	for (ll i = 2; i < 100000; i++) {
		if (sieve[i]) continue;
		for (ll j = i * i; j < 100000; j += i) sieve[j] = 1;
	}

	for (ll i = 2; i < 100000; i++) {
		if (!sieve[i]) primes.emplace_back(i);
	}

	cin >> N >> K;
	while (N--) {
		bool chk = 1;
		ll x; cin >> x;
		if (x == 1) {
			cout << "YES\n";
			continue;
		}
		else if (x <= K) {
			cout << "NO\n";
			continue;
		}

		for (auto& p : primes) {
			if (p > K || p * p > x) break;
			if ((x % p) == 0) {
				chk = 0;
				break;
			}
		}

		char old = '?'; int combo = 0;
		string s = to_string(x);
		for (auto& l : s) {
			if (l == old) combo++;
			else {
				if (combo > 3) chk = 0;
				old = l, combo = 1;
			}
		}
		if (combo > 3) chk = 0;

		if (chk) cout << "YES\n";
		else cout << "NO\n";
	}
}