[JAVA 알고리즘]BAEKJOON 27172번 수 나누기 게임

수 나누기 게임

---

문제 설명

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

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

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

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

입력

첫 번째 줄에 플레이어의 수 𝑁이 주어집니다.

두 번째 줄에 첫 번째 플레이어부터 𝑁번째 플레이어까지 각 플레이어가 가지고 있는 카드에 적힌 정수 𝑥1, ⋯, 𝑥𝑁이 공백으로 구분되어 주어집니다.

출력

첫 번째 플레이어부터 𝑁번째 플레이어까지 게임이 종료됐을 때의 각 플레이어의 점수를 공백으로 구분하여 출력해주세요.

제한사항

•  2 ≤ 𝑁 ≤ 100000
• 모든 1 ≤ 𝑖 ≤ 𝑁에 대해 1 ≤ 𝑥𝑖 ≤ 1000000입니다.
• 모든 1 ≤ 𝑖 < 𝑗 ≤ 𝑁에 대해 𝑥𝑖 ≠ 𝑥𝑗입니다. 즉, 어떤 수도 𝑥에서 두 번 이상 등장하지 않습니다.

입출력 예

input	return
3 3 4 12	1 1 - 2
4 7 23 8 6	0 0 0 0

---

문제 분석

플레이어 수가 100,000으로 브루트포스 알고리즘을 사용하면 경우의 수가 많아 경우의 수를 줄이는 방법을 사용해야 한다.

카드끼리 비교를 하는 게 아닌 해당 카드를 기준으로 비교하는 방법으로 숫자끼리 비교를 시킨다.

나눠지는 수는 해당 수의 약수 또는 배수라고 생각할 수 있다.

이를 소수를 구할 때와 같이 해당 수를 기준으로 배수인 카드를 비교하면 경우의 수를 줄일 수 있다.

손으로 풀기

1. 플레이어의 카드정보를 배열에 입력한다.
2. 카드의 가장 큰 수만큼 카드 배열을 만들어 카드를 가지고 있는 플레이어 위치를 입력한다.
3. 플레이어의 카드를 반복한다.
4. 해당 카드의 배수를 반복하면서 카드에 플레이어가 있을 경우, 해당 카드 플레이어의 점수를 증가시키고 배수 카드의 플레이어 점수를 감소시킨다.

나의 문제풀이

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        // 플레이어의 수
        int N = Integer.parseInt(bufferedReader.readLine());

        // 카드 정보 입력
        int[] player = new int[N];
        int maxCard = 0;
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for (int i = 0; i < N; i++) {
            player[i] = Integer.parseInt(stringTokenizer.nextToken());
            maxCard = Math.max(maxCard, player[i]) + 1;
        }

        // 카드별 플레이어 위치 입력
        int[] card = new int[maxCard];
        for (int i = 0; i < N; i++) {
            card[player[i]] = i + 1;
        }

        // 플레이어가 가진 카드의 배수가 되는 플레이어가 있으면 점수를 측정해준다.
        int[] score = new int[N];
        for (int num : player) {
            for (int j = num * 2; j < maxCard; j += num) {
                if (card[j] != 0) {
                    score[card[num] - 1]++;
                    score[card[j] - 1]--;
                }
            }
        }

        StringBuilder stringBuilder = new StringBuilder();
        for (int i : score) {
            stringBuilder.append(i).append(" ");
        }

        System.out.println(stringBuilder);
    }
}

---

알고리즘 분류

• 수학
• 브루트포스 알고리즘
• 정수론
• 소수 판정
• 에라토스테네스의 체

문제 출처 - https://www.acmicpc.net/problem/27172