취미로 코딩하기

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

이번에 볼 문제는 백준 2014번 문제인 소수의 곱이다.
문제는 아래 링크를 확인하자.

어떤 양의 정수 \(k\)에 대하여 \(k\)가 증가할 때 주어진 소수들의  곱으로 표현할 수 있는 \(k\) 이하의 양의 정수의 개수는 증가하거나 그대로 유지된다. 따라서, 그 개수를 빠르게 구할 수 있다면 이분탐색으로 문제의 답을 구할 수 있음을 관찰하자. 이제 이 개수를 빠르게 계산할 수 있는 방법을 생각해보자.

가능한 한 가지 방법으로 DP가 있다. 구체적으로, 모든 양의 정수는 가장 큰 소인수가 존재함을 이용해 상태를 정의하고, 이를 이용해 dp로 문제를 해결할 수 있다.

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

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

ll N, K;
ll P[100];
ll L = 1, R = 2147483647;

map<pair<ll, int>, ll> dp;

ll func(ll X, ll idx) {
	if (idx == N || X < P[idx]) return 1;
	if (dp.count(make_pair(X, idx))) return dp[make_pair(X, idx)];
	ll val = 0;
	for (ll x = 1; x <= X; x *= P[idx]) {
		val += func(X / x, idx + 1);
		if (val > K) {
			val = K + 1;
			break;
		}
	}
	return dp[make_pair(X, idx)] = val;
}

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

	cin >> N >> K;
	for (int i = 0; i < N; i++) cin >> P[i];
	while (L < R) {
		ll mid = (L + R) / 2;
		if (func(mid, 0) - 1 < K) L = mid + 1;
		else R = mid;
	}
	cout << L;
}