BOJ 32105 James Ferraro - Live at Primavera Sound 2012

문제 링크입니다.

문제 요약

$N$ 이하의 양의 정수를 둘씩 매칭해 합이 두 소수의 곱이 되는 쌍의 수를 최대화하세요.

풀이

$N$개의 정수를 둘씩 매칭하므로 가능한 답의 최댓값은 $\lfloor {N \over 2} \rfloor$입니다. 적당히 큰 $N$에 대해 이것이 실제로 가능함을 보입시다.

수학적 강귀납법을 이용합니다. 2를 제외한 $N$ 이하의 임의의 음이 아닌 정수 $k$에 대한 답이 $\lfloor { k \over 2} \rfloor$일 때, $N+1$에 대한 답 역시 ${\lfloor {N+1 \over 2} \rfloor}$임을 보이면 됩니다. 초기 상태로는 $N \le 7$에 대해서 실제로 그러한 해가 있음을 손으로 찾아줄 수 있습니다.

$N$이 홀수인 경우는 자명하게 성립하므로 짝수인 경우만 고려합시다. 임의의 짝수 $N \gt 7$에 대해 길이 $N-2$ 미만인 접미사가 매칭 가능하다면 수학적 강귀납법에 의해 $N$과 $N+1$에서 역시 최대 매칭이 가능함을 알 수 있습니다. 값을 남기지 않고 매칭하려면 짝수 길이의 접미사만 활용하는 것이 편합니다.

어렵게 매칭을 찾는 대신에, 적당한 두 홀수 소수의 곱을 찾아 그를 중심으로 매칭하는 방식으로 접근합시다. 그러면 사용할 수 있는 두 소수의 곱의 범위는 $N+3$ 초과 $2N-1$ 이하 (즉 $2N+1$ 미만)입니다.

베르트랑 공준에 의해, 2 이상의 임의의 정수 $n$에 대해, $n \lt p \lt 2n$인 소수 $p$가 반드시 존재합니다. 현재 우리가 가진 범위 조건은 두 소수의 곱에 대한 정보이므로, 하나의 소수에 대한 정보로 줄이기 위해 범위를 작은 홀수 소수 3으로 나누면 다음의 결과를 얻습니다.

\[ \lfloor {N+3 \over 3} \rfloor \lt p \lt \lceil {2N+1 \over 3} \rceil \]

상황에 따라 upper bound가 한 칸씩 모자란 거 아닌가 하는 의문이 들 수 있는데, 실제로 모자라긴 합니다(??). 다만 어느 정도 큰 $N$에 대해서는(간단한 bound로는 $N \gt 72$ 정도가 있습니다.) 저 범위로도 충분히 성립합니다. 작은 값들에 대해서는 인접한 두 수의 곱이 $3p$ 꼴인 위치들을 적당히 찾아보면 $N$과 $3$을 매칭하기 전에 항상 다른 쌍을 찾을 수 있다는 점을 확인할 수 있습니다.

그래서 위의 방식대로 $N$부터 역순으로 매칭할 값을 찾아주는 그리디한 해 구성 전략이 먹힙니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

bool isp[101010]={1,1};

vector<pll> base[8];
vector<pll> ans;

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	base[3].push_back({1, 3});
	base[4].push_back({1, 3}); base[4].push_back({2, 4});
	base[5].push_back({1, 3}); base[5].push_back({2, 4});
	base[6].push_back({1, 5}); base[6].push_back({3, 6}); base[6].push_back({2, 4});
	base[7].push_back({1, 5}); base[7].push_back({3, 6}); base[7].push_back({2, 4});
	for(int i = 2; i*i <= 100000; i++) if(!isp[i]) for(int j = i*i; j <= 100000; j += i) isp[j] = 1;
	int n; cin >> n;
	for(int L = n; L >= 1; L--){
		if(n <= 7) break;
		if((L+n)%3 == 0 && !isp[(L+n)/3]){
			for(int i = L, j = n; i < j; i++, j--) ans.push_back({i, j});
			n = L-1;
		}
	}
	cout << ans.size()+base[n].size() << '\n';
	for(auto [x, y] : base[n]) cout << x << ' ' << y << '\n';
	for(auto [x, y] : ans) cout << x << ' ' << y << '\n';
}