[백준 / BOJ] C++ 14622 소수 게임

14622번: 소수 게임

 

문제

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

14622번: 소수 게임

 

 

풀이

에라토스테네스의 체로 미리 500만 이하의 소수를 구해놓은 다음, 입력 범위를 주의하며 차례대로 조건에 따라 구현하면 되는 문제다. 입력받은 수에 따라 조건을 나누어보겠다.

 

1. 이미 등장한 소수인 경우

이미 등장한 소수인 경우엔 자신이 -1000점을 얻는다.

 

2. 처음 등장하는 소수인 경우

처음 등장한 소수인 경우엔 해당 소수를 방문처리하고 정렬이 오름차순인 우선순위 큐에 해당 수를 추가한다. N의 범위가 10만이므로 무한정 추가하면 범위가 초과될 것이 분명하기 때문에 크기가 3을 초과하면 가장 작은 값, 즉 top 원소를 제거해 주어 우선순위 큐의 크기를 3으로 유지한다.

 

3. 소수가 아닌 경우

마지막 경우는 소수가 아닌 경우다. 소수가 아닌 경우엔 상대방의 우선순위 큐의 크기를 확인해야한다. 우선순위 큐의 크기가 3 미만인 경우 상대방이 1000점을 얻는다. 우선순위 큐의 크기가 3인 경우엔 3번째로 큰 값, 즉 top 원소만큼 점수를 얻는다.

 

여기서 주의해야할 점은 우선순위 큐의 크기를 최대 3으로 유지한다는 점과 점수의 데이터 타입이 long long이어야 한다. 우선순위 큐의 크기를 작게 유지해야 하는 이유는 위에서 언급했듯이 10만 개의 수를 감당할 수 없기 때문이다. 그리고 입력되는 소수가 500만 이하인데 3번째로 작은 소수가 계속 점수에 추가되면 int의 범위를 넘길 수 있기 때문이다. 간단한 예로 상대방이 4999961, 4999963, 4999999를 불렀다고 했을 때(모두 소수다) 내가 소수가 아닌 수를 입력하면 상대방은 4999961점을 얻는다. 라운드가 10만 번 지난다면 4999961 × 100000 = 499996100000이므로 long long int를 사용해줘야 한다.

 

(long long을 사용하지 않아 여러 번 틀렸다.)

 

 

코드

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  // 에라토스테네스의 체
  vector<int> sieve(5000001, 1);
  for (int i = 2; i <= 5000000; i++)
    if (sieve[i])
      for (int j = i * 2; j <= 5000000; j += i)
        sieve[j] = 0;
  sieve[0] = 0, sieve[1] = 0;
  
  int n;
  long long a_sum = 0, b_sum = 0;
  cin >> n;
  vector<int> visited(5000001, 0);
  priority_queue<int, vector<int>, greater<int>> a, b;
  while (n--) {
    int num;
    // 대웅이 차례
    cin >> num;
    if (sieve[num]) { // 소수인 경우
      if (visited[num] == 0) { // 소수이면서 처음 나온 수인 경우
        visited[num] = 1;
        a.push(num);
        if (a.size() > 3)
          a.pop();
      } else { // 소수이면서 이미 나온 수인 경우
        a_sum -= 1000;
      }
    } else { // 소수가 아닌 경우
      if (b.size() < 3)
        b_sum += 1000;
      else
        b_sum += b.top();
    }
    // 규성이 차례
    cin >> num;
    if (sieve[num]) { // 소수인 경우
      if (visited[num] == 0) { // 소수이면서 처음 나온 수인 경우
        visited[num] = 1;
        b.push(num);
        if (b.size() > 3)
          b.pop();
      } else { // 소수이면서 이미 나온 수인 경우
        b_sum -= 1000;
      }
    } else { // 소수가 아닌 경우
      if (a.size() < 3)
        a_sum += 1000;
      else
        a_sum += a.top();
    }
  }
  if (a_sum > b_sum)
    cout << "소수의 신 갓대웅\n";
  else if (a_sum < b_sum)
    cout << "소수 마스터 갓규성\n";
  else
    cout << "우열을 가릴 수 없음\n";
  return 0;
}