백준 19595 (C++) 소수 게임

최초 업로드: 2025-10-01 11:22:09

최근 수정 시간: 2025-10-01 13:21:47

게시자: rlatjwls3333

카테고리: 백준

# [Gold II] 소수 게임

[문제 링크](https://www.acmicpc.net/problem/19595)

## 문제 설명

Alice와 Bob은 "소수 게임"을 즐겨한다.

소수 게임에서는 두 사람이 먼저 일정한 양의 정수 구간 (interval)을 먼저 고르고, 해당 구간에 속한 모든 정수 각각에 대해 미니 게임을 한 번씩 플레이 한다.

정확한 규칙은 아래와 같다.

<ul>
	<li>먼저, Alice가 두 개의 정수 A, k를 고른다 (이 때 2 ≤ k ≤ A-1 을 만족해야 한다). 
	k는 미니 게임을 몇 번 할지를 결정하고, A는 정수 구간의 상한값을 결정한다.</li>
	<li>다음으로 Bob이 2 ≤ x ≤ A + 1 - k를 만족하는 정수 x를 고른다. 
	x는 정수 구간의 하한값을 결정한다. 즉, x ≤ 정수구간 ≤ A가 된다. </li>
	<li>두 사람은 이제 미니 게임을 k번 플레이 하는데, x이상 x+k-1 이하의 정수 각각에 대하여 아래 미니 게임을 플레이한다 (각각의 미니 게임에서 고른 정수를 N이라 하자).
	<ul>
		<li>먼저, N을 종이에 적는다 (x ≤ N ≤ x+k-1). 그리고 Alice와 Bob이 번갈아 플레이 한다.</li>
		<li>Alice가 먼저 시작하여 종이에 적힌 숫자보다 크지 않은 수 중 소수 (prime) P를 고른다.</li>
		<li>종이에 적힌 수가 X라면, 이를 지우고 X-P를 종이에 새로 적는다. </li>
		<li>Bob의 차례가 되어 이를 반복한다.</li>
		<li>만약 자신의 차례가 되었을 때 종이에 적힌 수가 0이나 1이라면 진다. (다시 말해, X-P를 종이에 적을 때 이 값이 0이나 1이면 이긴다.)</li>
	</ul>
	</li>
</ul>

예를 들어 N = 8 이라면, Alice가 자신의 처음 차례에 7을 고르면 이긴다.

N = 10이라면 Alice가 자신의 차례에 고를 수 있는 소수는 2, 3, 5, 7 중 하나이다.

따라서 N = 10인 경우, Bob이 최선을 다한다면 Alice가 이길 방법은 없다. (두 사람은 언제나 최선을 다해서 플레이 한다고 가정하자.)

Bob은 A, k가 주어졌을 때 x를 잘 골라서 자신의 승률을 최대화 하기로 했다. 만약 승률을 최대화 하는 x값이 여럿이라면 그 중 가장 작은 x를 찾기로 했다. Bob을 도와주자.

## 입력

첫 줄에 테스트 케이스의 수 T가 주어진다.

각 줄에 A와 k가 공백으로 구분되어 주어진다.

## 출력

각 테스트 케이스에 대해 두 개의 정수를 공백으로 구분하여 출력한다.

첫 수는 k번의 게임 중 Bob이 최대 몇 번을 이길 수 있는지 나타내고, 두 번째 수는 이를 위해 Bob이 선택해야하는 x값 중 최소 값을 나타낸다.

## 풀이
에라토스테네스의 체로 소수를 미리 구해 놓고, 게임이론 + dp로 승리하는 사람을 미리 구하고, 누적합으로 범위를 빠르게 찾았습니다. 관련된 문제 3개를 합쳐 놓은 느낌입니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAX = 100'001;

bool win[MAX];
int preSum[MAX], notSosu[MAX];
vector<int> sosu;

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 for(int i=2;i*i<MAX;i++) {
 if(!notSosu[i]) {
 for(int j=i*i;j<MAX;j+=i) notSosu[j]=true;
 }
 }
 for(int i=2;i<MAX;i++) {
 if(!notSosu[i]) sosu.push_back(i);
 }

fill(win, win+MAX, 1);
 for(int i=0;i<MAX;i++) {
 if(i) preSum[i] = preSum[i-1];
 if(win[i]) {
 if(i>=2) preSum[i]++;
 for(int e : sosu) {
 if(i+e>=MAX) break;
 win[i+e]=0;
 }
 }
 }

int t; cin >> t;
    while(t--) {
        int a, k; cin >> a >> k;

int x=2;
 for(int i=2;i<=a+1-k;i++) {
 if(preSum[i+k-1]-preSum[i-1] > preSum[x+k-1]-preSum[x-1]) x = i;
 }
 cout << preSum[x+k-1]-preSum[x-1] << ' ' << x << '\n';
 }
}
```