[BOJ] 27172 수 나누기 게임 (node.js)

BOJ 문제 27172번의 풀이 과정을 작성한 게시글입니다.

 

링크

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

 

문제

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

 

게임을 시작하기 전 각 플레이어는 1부터 1000000 사이의 수가 적힌 서로 다른 카드를 잘 섞은 뒤 한 장씩 나눠 가집니다.

매 턴마다 플레이어는 다른 플레이어와 한 번씩 결투를 합니다.

결투는 서로의 카드를 보여주는 방식으로 진행되며, 플레이어의 카드에 적힌 수로 다른 플레이어의 카드에 적힌 수를 나눴을 때, 나머지가 0$0$이면 승리합니다. 플레이어의 카드에 적힌 수가 다른 플레이어의 카드에 적힌 수로 나누어 떨어지면 패배합니다. 둘 다 아니라면 무승부입니다.

승리한 플레이어는 1점을 획득하고, 패배한 플레이어는 1점을 잃습니다. 무승부인 경우 점수의 변화가 없습니다.

본인을 제외한 다른 모든 플레이어와 정확히 한 번씩 결투를 하고 나면 게임이 종료됩니다.

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

 

풀이 과정

접근법 1. 조합

모든 플레이어들이 한 번씩 게임을 진행해야 하기 때문에,

가장 간단하게는 모든 플레이어들의 게임을 모두 한 번씩 진행시키는 방법이 있다.

 

하지만 이는 전체 인원이 최대 10,000명인 것을 고려하면 시간 초과가 발생하게 된다.

 

접근법 2. 각 수의 배수를 구해서 처리하기

게임에서 이기는 경우와 지는 경우를 정리하면 다음과 같다.

나	A	B
3	6	12

 

나와 A가 결투를 할 때

6을 3으로 나눈 나머지는 0이므로 내가 승리한다.

그리고 A는 패배한다.

 

나와 B가 결투를 할 때도 마찬가지로

12를 3으로 나눈 나머지는 0이므로 내가 승리한다.

그리고 B는 패배한다.

 

즉, 내가 이기는 경우의 수는 내 카드의 배수가 되는 수를 다른 참가자들이 몇개를 가지고 있는지를 통해 승리 횟수를 미리 구할 수 있다.

 

나는 현재 플레이어 카드의 배수가 되는 수를 순회하면서,

배수가 다른 플레이어 중에서 존재한다면 승리 횟수를 높이고, 반대로 해당 배수의 패배 횟수를 추가(점수에 -1)했다.

 

 

코드

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = require("fs").readFileSync(filePath).toString().trim().split("\n");

const nums = input[1].split(" ").map(Number);
const isExist = Array.from({ length: 1000001 }, () => false);
const score = Array.from({ length: 1000001 }, () => 0);

for (let num of nums) {
  isExist[num] = true;
}

for (let num of nums) {
  for (let i = num * 2; i <= 1000000; i += num) {
    if (isExist[i]) {
      score[num]++;
      score[i]--;
    }
  }
}

const answer = [];

for (let num of nums) {
  answer.push(score[num]);
}

console.log(answer.join(" "));

 

후기

처음에는 n^2라고 생각해서 시간 초과가 날 수도 있겠다고 생각했는데, 이중 포문 내부의 연산 횟수가 n이 아니라 logn에 가깝기 때문에 시간 초과가 발생하지 않았다.