[BOJ/Gold 4] 백준 14622 소수 게임(C++)

문제 링크

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

 

문제

인하대학교에 다니는 대웅이는 정수론을 정말 좋아한다. 정수론을 광적으로 좋아하는 대웅이는 어느 순간부터 소수를 외우기 시작했고 어떤 수를 말하면 그 수가 소수인지 아닌지 판별할 수 있는 능력을 가지게 되었다. 인하대학교에 소수의 신이 있다는 소문이 퍼지자 인상대학교의 소수 마스터 규성이는 대웅이에게 도전장을 내밀었다.

둘은 누가 더 소수를 사랑하는지 내기를 하기로 하였다.

하지만 누가 더 소수를 사랑하는지에 대한 기준이 없으므로 소수 게임을 이용하기로 하였다.

소수게임의 규칙은 다음과 같다. 

 

1. 두 사람이 번갈아가며 소수를 말한다.
2. 소수가 아닌 수를 부르게 될 경우 상대방은 지금까지 상대방이 말한 소수중에서 3번째로 큰 수만큼 점수를 얻게 된다.(만약 상대방이 지금까지 말한 소수가 3개 미만이라면 상대방은 1000점을 얻게 된다.)
3. 만약 지금까지 한번이라도 등장한 소수를 말할 경우 해당 소수를 말한 팀이 -1000을 얻게 되며 해당 소수는 그 사람이 말한 소수로 기록되지 않는다.
4. 규성이는 도전자이므로 게임은 항상 대웅이부터 시작한다.
5. 두 사람이 말할 수 있는 소수는 항상 5000000 미만이다.

다음과 같은 규칙으로 소수 게임을 진행할 때 승자를 출력하시오. 

 

입력

입력의 첫째 줄에 두 사람이 대결을 하는 라운드 수 N이 주어진다. (5 ≤ N ≤ 100,000)

이 후 N개의 줄에 대웅이와 규성이가 말하는 정수가 공백으로 구분되어 주어진다. 두 사람이 말하는 정수는 5,000,000보다 작은 자연수 또는 0이다.

 

출력

대웅이가 이길 경우 “소수의 신 갓대웅” 규성이가 이길 경우 “소수 마스터 갓규성”을 출력한다. 만약 비길 경우 “우열을 가릴 수 없음” 을 출력한다.

 

예제 입력 1

5
2 3
4 9
2 10
7 37
11 3

예제 출력 1

소수의 신 갓대웅

 

알고리즘 분류

• 소수 판정

 

풀이

최소 힙 우선순위 큐를 이용해서 두 사람이 각자 부른 소수를 관리한다. 이 때, 부른 소수 중 세 번째로 큰 수가 Top으로 오게 하기 위해서 우선순위 큐의 크기가 3이 될 때까지 Top을 전부 pop해준다.

또한 부를 수 있는 최대 수가 500만이고, 최대 10만 번을 부를 수 있기 때문에 최대로 얻을 수 있는 점수가 5,000억에 근접할 것이므로 점수를 long 자료형으로 관리한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <algorithm>
#define MAX 5000001
#define LL long long
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, A, B;
int DP[MAX];
bool Visited[MAX];
priority_queue<int, vector<int>, greater<int> > PQ1, PQ2;
LL AnswerA, AnswerB;

void init() {
	for (int i = 2; i < MAX; i++) {
		DP[i] = i;
	}
	for (int i = 2; i <= sqrt(MAX); i++) {
		if (DP[i] == 0) continue;
		for (int j = (i * i); j < MAX; j += i) {
			DP[j] = 0;
		}
	}
}

void settings() {
	if (DP[A] == 0) {
		if ((int)PQ2.size() < 3) {
			AnswerB += 1000L;
		}
		else {
			AnswerB += (LL)PQ2.top();
		}
	}
	else {
		if (Visited[A]) {
			AnswerA -= 1000L;
		}
		else {
			Visited[A] = true;
			PQ1.push(A);
			while ((int)PQ1.size() > 3) {
				PQ1.pop();
			};
		}
	}

	if (DP[B] == 0) {
		if ((int)PQ1.size() < 3) {
			AnswerA += 1000L;
		}
		else {
			AnswerA += (LL)PQ1.top();
		}
	}
	else {
		if (Visited[B]) {
			AnswerB -= 1000L;
		}
		else {
			Visited[B] = true;
			PQ2.push(B);
			while ((int)PQ2.size() > 3) {
				PQ2.pop();
			};
		}
	}
}

void input() {
    cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A >> B;
		settings();
	}
}

void printAnswer() {
	if (AnswerA > AnswerB) {
		cout << "소수의 신 갓대웅\n";
	}
	else if (AnswerA < AnswerB) {
		cout << "소수 마스터 갓규성\n";
	}
	else {
		cout << "우열을 가릴 수 없음\n";
	}
}

int main() {
    FASTIO

	init();
    input();
    printAnswer();

    return 0;
}