[백준] 27172: 수 나누기 게임 (에라토스테네스의 체) - JAVA

class 5

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

 

 

# 문제

《보드게임컵》을 준비하다 지친 은하는 보드게임컵 참가자들을 경기장에 몰아넣고 결투를 시키는 게임 《수 나누기 게임》을 만들었습니다.

《수 나누기 게임》의 규칙은 다음과 같습니다.

• 게임을 시작하기 전 각 플레이어는 1$1$부터 1000000$1\,000\,000$ 사이의 수가 적힌 서로 다른 카드를 잘 섞은 뒤 한 장씩 나눠 가집니다.
• 매 턴마다 플레이어는 다른 플레이어와 한 번씩 결투를 합니다.
• 결투는 서로의 카드를 보여주는 방식으로 진행되며, 플레이어의 카드에 적힌 수로 다른 플레이어의 카드에 적힌 수를 나눴을 때, 나머지가 0$0$이면 승리합니다. 플레이어의 카드에 적힌 수가 다른 플레이어의 카드에 적힌 수로 나누어 떨어지면 패배합니다. 둘 다 아니라면 무승부입니다.
• 승리한 플레이어는 1$1$점을 획득하고, 패배한 플레이어는 1$1$점을 잃습니다. 무승부인 경우 점수의 변화가 없습니다.
• 본인을 제외한 다른 모든 플레이어와 정확히 한 번씩 결투를 하고 나면 게임이 종료됩니다.

《수 나누기 게임》의 결과를 가지고 한별이와 내기를 하던 은하는 게임이 종료되기 전에 모든 플레이어의 점수를 미리 알 수 있을지 궁금해졌습니다. 은하를 위해 각 플레이어가 가지고 있는 카드에 적힌 수가 주어졌을 때, 게임이 종료된 후의 모든 플레이어의 점수를 구해주세요.

 

 

# 예제

입력 : 

첫 번째 줄에 플레이어의 수 N$N$이 주어집니다. 두 번째 줄에 첫 번째 플레이어부터 N$N$번째 플레이어까지 각 플레이어가 가지고 있는 카드에 적힌 정수 x1$x_{1}$, ⋯$\cdots$, xN$x_{N}$이 공백으로 구분되어 주어집니다.

3
3 4 12

 

출력

1 1 -2

 

 

# 필요개념

원래는 이중 for문으로 직접 두 수의 나머지를 확인하려고 했으나 시간초과가 발생했다.

 

 

그러다가 에라토스테네스의 체를 알게 되었다.

 

 

에라토스테네스의 체

이것은 소수를 구하는 가장 정확한 방법으로 알려져있다. 2부터 자신의 배수를 점차 지워가면 남은 수들이 소수가 된다는 이론이다. 이 이론을 이용해서 문제풀이를 진행했다.

 

input배열로 수를 입력받고, 최대값을 저장해둔다. input으로 들어온 수의 배수를 확인하는데, 이는 최대값보다 같거나 작은 범위만 보면 되기 때문이다! 

 

배수들 중 input에 들어있던 값을 발견하면, 문제 조건에 맞기 점수를 조정한다.

 

# Code

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] inputs = new int[N];
        int max = Integer.MIN_VALUE;
        for (int i = 0 ; i < N ; i++) {
            inputs[i] = Integer.parseInt(st.nextToken());
            max = Math.max(max, inputs[i]);
        }
        int[] score = new int[N + 1];
        int[] index = new int[max + 1];

        for (int i = 0 ; i < N ; i++) {
            index[inputs[i]] = i + 1;
        }

        for (int obj : inputs) {
            for (int i = 2 * obj ; i <= max ; i += obj) {
                if (index[i] != 0) {
                    score[index[i]]--;
                    score[index[obj]]++;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 1 ; i <= N ; i++) {
            sb.append(score[i]).append(" ");
        }
        System.out.println(sb.toString());
    }
}

 

# 결과