[백준] 25632번 소수부르기게임 - 자바스크립트

문제

25632번: 소수 부르기 게임

새로 나온 따끈따끈한 문제에,, 실버4 난이도 치고는 생각할 게 조금 있어서 가져오게 되었다.

---

코드

function sol(input) {
  const [A, B] = input[0].split(' ').map(Number);
  const [C, D] = input[1].split(' ').map(Number);

  const yt = eratosThenes(A, B);
  const yj = eratosThenes(C, D);
  const ytPrimes = {};
  let intersection = 0;

  yt.forEach((prime) => (ytPrimes[prime] = 1));
  yj.forEach((prime) => {
    if (ytPrimes[prime]) intersection++;
  });

  const cnt = { yt: yt.length, yj: yj.length };

  while (cnt.yt > 0 && cnt.yj > 0) {
    if (intersection >= 2) {
      intersection -= 2;
      cnt.yt -= 2;
      cnt.yj -= 2;
    } else if (intersection >= 1) {
      intersection--;
      cnt.yt -= 1;
      cnt.yj -= 2;
    } else {
      cnt.yt -= 1;
      cnt.yj -= 1;
    }
  }

  return cnt.yt > cnt.yj ? 'yt' : 'yj';
}

function eratosThenes(start, end) {
  const arr = Array.from({ length: 1001 }, (_, i) => i);
  const sqrt = Math.floor(arr.length);
  arr[1] = 0;

  for (let i = 2; i <= sqrt; i++) {
    if (arr[i] === 0) continue;

    for (let j = 2 * i; j <= 1000; j += i) {
      arr[j] = 0;
    }
  }

  return arr.slice(start, end + 1).filter((elem) => elem);
}



const input = [];
require('readline')
  .createInterface(process.stdin, process.stdout)
  .on('line', (line) => {
    input.push(line);
  })
  .on('close', () => {
    console.log(sol(input));
    process.exit();
  });

 

---

풀이

 

조건

용태는 범위 A,B 내에 있는 소수를 부른다.

유진이는 범위 C,D 내에 있는 소수를 부른다.

용태부터 시작해 서로 번갈아가며 부를 수 있는 범위의 소수를 부른다. 그러나 중복되선 안된다.

더이상 소수를 부를 수 없다면 패배한다.

 

2 <= A <= B <= 1000

2 <= C <= D <= 1000

 

Q. "용태와 유진이가 모두 최선을 다해 게임을 플레이 했을 때 누가 이길까?"

 

풀이방향

keypoint : "최선을 다해야 하므로" 용태/유진이의 소수 교집합을 먼저 불러야 한다.

 

1. 각자의 소수 구하는 방법을 이용해서 A,B범위, C,D 범위의 소수들을 구한다.

2. 각자의 방법으로 용태와 유진이의 소수 교집합을 구한다.

    나는 용태 소수들을 먼저 기록하고, 유진이도 동일한 소수를 가지고 있다면 카운팅했다.

3. 먼저 소수 교집합을 소진시키고, 각자의 소수들을 소진시킨다.

4. 용태, 유진이가 각각 소수를 한번씩 부르는 것을 1개의 사이클로 한다.

    둘 다 부를 소수가 없다면, 용태 순서이므로 용태가 패배함을 유의한다.

 

---

주석포함

function sol(input) {
  const [A, B] = input[0].split(' ').map(Number);
  const [C, D] = input[1].split(' ').map(Number);

  const yt = eratosThenes(A, B); // 용태의 소수
  const yj = eratosThenes(C, D); // 유진이의 소수
  const ytPrimes = {};
  let intersection = 0;

  yt.forEach((prime) => (ytPrimes[prime] = 1));
  yj.forEach((prime) => {
  	// 유진이의 소수가 용태의 소수면 소수교집합 카운트
    if (ytPrimes[prime]) intersection++;
  });

  const cnt = { yt: yt.length, yj: yj.length };

  while (cnt.yt > 0 && cnt.yj > 0) {
  	// 1개 사이클에 각자 번갈아가며 숫자를 불러줘야 함.
    if (intersection >= 2) {
    	// 교집합이 있다면 먼저 소진.
      intersection -= 2;
      cnt.yt -= 2;
      cnt.yj -= 2;
    } else if (intersection >= 1) {
        // 교집합이 1개 남았다면, 용태만 소진하고 유진이는 자신의 소수 부름.
      intersection--;
      cnt.yt -= 1;
      cnt.yj -= 2;
    } else {
	    // 	교집합이 없다면 각자의 소수 부름.
      cnt.yt -= 1;
      cnt.yj -= 1;
    }
  }
	
    // == 을 포함하면 용태가 부를차례에 남은 수가 없음에도 이기게 되어 실패
  return cnt.yt > cnt.yj ? 'yt' : 'yj';
}


function eratosThenes(start, end) {
	// 각자의 방법으로 구간 내의 소수를 구하는 공식을 써보자.
  const arr = Array.from({ length: 1001 }, (_, i) => i);
  const sqrt = Math.floor(arr.length);
  arr[1] = 0;

  for (let i = 2; i <= sqrt; i++) {
    if (arr[i] === 0) continue;

    for (let j = 2 * i; j <= 1000; j += i) {
      arr[j] = 0;
    }
  }

  return arr.slice(start, end + 1).filter((elem) => elem);
}



const input = [];
require('readline')
  .createInterface(process.stdin, process.stdout)
  .on('line', (line) => {
    input.push(line);
  })
  .on('close', () => {
    console.log(sol(input));
    process.exit();
  });

조금 더 쉽고 간단한 방법이 존재할 수 있습니다!