백준 14622번: 소수 게임 (Java)

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

14622번: 소수 게임

 

 

 

 

 

 

 

 

---

 

풀이

에라토스테네스를 이용하여 500만 미만의 소수를 저장합니다. 또한, 특정 소수를 방문했는지 기록할 boolean 배열도 하나 선언해줍시다. 대웅이와 규성이가 번갈아가면서, 1) 소수가 아닌 수를 불렀는지, 2) 이미 부른 소수를 불렀는지, 3) 한 번도 안 부른 소수를 불렀는지를 체크하여 문제 조건대로 처리해줍니다.

N은 최대 10만이기에, 3번째로 큰 소수를 배열같은 곳에 저장하면 당연히 시간초과가 뜰 것입니다. 각자가 부른 상위 3개의 소수를 우선순위 큐에 담아 두어, 3번째로 큰 소수를 O(1)에 호출하고, 갱신을 O(log3)에 수행하도록 합니다.

단순 에라토스테네스의 체를 활용하는 문제에서 자료구조에 대해 생각해보아야 하며, 구현 능력도 살짝 요구하는 재미있는 문제입니다. 다만 문제 디스크립션이 살짝 아쉽네요.

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
    
    static boolean[] isPrime;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        sieve(5000000);
        boolean[] visited = new boolean[5000001];
        long dw = 0, gs = 0; // 대웅, 규성의 점수를 저장하는 변수
        // 대웅, 규성이 부른 상위 3개의 소수를 저장하는 우선순위 큐
        PriorityQueue<Integer> dws = new PriorityQueue<>(); 
        PriorityQueue<Integer> gss = new PriorityQueue<>();
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int d = Integer.parseInt(st.nextToken());
            int g = Integer.parseInt(st.nextToken());
            
            // 대웅 먼저
            // 소수가 아닌 수를 부름
            if (!isPrime[d]) {
                if (gss.size() == 3) {
                    gs += gss.peek();
                } else {
                    gs += 1000;
                }
            }
            // 소수이나 이미 부른 수를 말함
            else if (visited[d]) {
                dw -= 1000;
            } 
            // 그 외: 한 번도 안 부른 소수를 말함
            else {
                visited[d] = true;
                if (dws.size() < 3) {
                    dws.offer(d);
                } else {
                    if (dws.peek() < d) {
                        dws.poll();
                        dws.add(d);
                    }
                }
            }
            
            // 규성 차례
            if (!isPrime[g]) {
                if (dws.size() == 3) {
                    dw += dws.peek();
                } else {
                    dw += 1000;
                }
            }
            else if (visited[g]) {
                gs -= 1000;
            } 
            else {
                visited[g] = true;
                if (gss.size() < 3) {
                    gss.offer(g);
                } else {
                    if (gss.peek() < g) {
                        gss.poll();
                        gss.add(g);
                    }
                }
            }
        }
        if (dw > gs) System.out.println("소수의 신 갓대웅");
        else if (dw < gs) System.out.println("소수 마스터 갓규성");
        else System.out.println("우열을 가릴 수 없음");
    }
 
    static void sieve(int N) {
        isPrime = new boolean[N+1];
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;
        for (int i = 2; i*i <= N; i++) {
            if (isPrime[i]) {
                for (int j = 2*i; j < N+1; j += i) {
                    isPrime[j] = false;
                }
            }
        }
    }
}