[백준] 27172 - 수 나누기 게임

1. 문제

27172번: 수 나누기 게임

2. 개요

보드게임 대회에서 수 나누기 게임을 진행한다.

게임의 규칙은 다음과 같다.

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

각 플레이어가 들고 있는 카드의 정보가 주어졌을 때, 게임이 끝난 뒤 모든 플레이어의 점수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

결투하는 플레이어를 각각 x, y라고 했을 때, y가 x의 배수라면 x의 승리, y의 패배로 결정난다.

이를 이용하여 소수를 구하듯이 테이블에서 배수를 찾아나가면서 만약 y가 x의 배수라면 결투의 결과에 따른 점수를 갱신해나가면 된다.

3-2. Python

import sys

N = int(sys.stdin.readline())

chk = [False for i in range(1000001)]
result = [0 for i in range(1000001)]

nums = list(map(int, sys.stdin.readline().split()))

for num in nums:
    chk[num] = True

for num in sorted(nums):
    for j in range(num * 2, 1000001, num):
        if chk[j] == True:
            result[num] += 1
            result[j] -= 1

for i in range(N):
    print(result[nums[i]], end = " ")

3-3. C#

namespace boj_27172
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            int N = int.Parse(sr.ReadLine());

            bool[] chk = new bool[1000001];
            int[] result = new int[1000001];

            int[] nums = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);

            for (int i = 0; i < N; i++)
                chk[nums[i]] = true;

            foreach (int num in nums.OrderBy(x => x).ToArray())
            {
                for (int j = num * 2; j < 1000001; j += num)
                {
                    if (chk[j] == true)
                    {
                        result[num]++;
                        result[j]--;
                    }
                }
            }

            for (int i = 0; i < N; i++)
            {
                sw.Write($"{result[nums[i]]} ");
            }

            sw.Close();
        }
    }
}