문제 링크

성능 요약

메모리: 46144 KB, 시간: 572 ms

분류

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

제출 일자

2025년 1월 10일 14:24:53

문제 설명

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

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

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

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

입력

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

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

출력

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

풀이

• 문제 입력예시를 잘 확인해야한다. 입력이 오름차순이 아닐 수 있다.
• 처음 입력된 수를 정렬하지만, 출력할때는 입력된 순서대로 출력해야해서 복사본을 만들었다.
• 깔끔하지 않은 풀이같다. 더 효율적인 방법이 있을 것 같다.

설계 : 20분

• 입력된 수들을 오름차순으로 정렬(복사본)한 후 거꾸로 순회하며 수의 존재여부를 기록하고, 최대값에 이르기까지 자기자신을 반복해서 더해가며 존재하는 배수들을 카운트 한다.

코드(Java)

• 구현 시간: 40분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 수 나누기 게임_27172
 * Date: 2025.01.10
 */

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

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.parseInt(br.readLine());
        String[] input = br.readLine().split(" ");
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) nums[i] = Integer.parseInt(input[i]);
        int[] copy = Arrays.copyOf(nums, n);
        Arrays.sort(copy);

        int max = copy[n-1];
        boolean[] exist = new boolean[max + 1];
        int[] score = new int[max + 1];

        for (int i = n-1; i >= 0; i--) {
            exist[copy[i]] = true;

            int mult = copy[i] + copy[i];
            while (mult <= max) {
                if (exist[mult]) {
                    score[copy[i]]++;
                    score[mult]--;
                }
                mult += copy[i];
            }
        }

        for (int i = 0; i < n; i++) bw.write(String.valueOf(score[nums[i]]) + " ");
		bw.flush();
		bw.close();
		br.close();
	}
}