취미로 코딩하기

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

이번에 볼 문제는 백준 11381번 문제인 Sequences이다.

문제는 아래 링크를 확인하자.

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

1보다 크고 서로 소인 두 양의 정수 x1과 x2에 대하여 a*x1+b*x2(a>0,b>0, a와 b는 정수) 꼴로 나타내지 못하는 가장 큰 양의 정수는 x1*x2-x1-x2임이 잘 알려져있다. 증명은 생략한다. 이것으로 서브태스크2를 해결할 수 있다.

조건에 따라 x1은 1000보다 작다. 따라서 각 1이상 x1 미만의 수 k에 대해 다른 xn들의 합으로 나타나는 수 중 가장 작은 수를 dijkstra 알고리즘을 이용해 구할 수 있다. 이렇게 구한 수에서 x1을 뺀 수는 x1으로 나누었을 때 나머지가 k인 수중 만들 수 없는 가장 큰 수가 되므로, x1개의 정답 후보를 비교하는 것으로 문제를 해결할 수 있다. 이 과정에서 64비트 정수 자료형을 벗어나는 답안이 나올 수 없다는 것은 위 문단의 공식과 문제 조건으로 알 수 있다.

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

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

int N;
ll num[5];
ll arr[1000];
priority_queue<ll> pq;

void solve() {
	ll n0 = num[0];
	arr[0] = n0;
	for (int i = 1; i < N; i++) pq.push(-num[i]);
	while (!pq.empty()) {
		ll cur = -pq.top(); pq.pop();
		if (arr[cur % n0]) continue;
		arr[cur % n0] = cur;
		for (int i = 1; i < N; i++) {
			if (arr[(cur + num[i]) % n0]) continue;
			pq.push(-(cur + num[i]));
		}
	}
	ll ans = 0;
	for (ll i = 0; i < n0; i++) {
		ans = max(ans, arr[i]);
	}
	cout << ans - n0;
}

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

	cin >> N;
	for (int i = 0; i < N; i++) cin >> num[i];
	if (N == 2) cout << num[0] * num[1] - num[0] - num[1];
	else solve();
}