백준 9657 < 돌 게임 3 > JavaScript

📍유사 문제

2023.01.13 - [⚙️알고리즘 & 자료구조/BOJ] - 백준 9655 < 돌 게임 > JavaScript

백준 9655 < 돌 게임 > JavaScript

 

📍문제 링크

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

9657번: 돌 게임 3

 

📍알고리즘 분류

- 다이나믹 프로그래밍

- 게임 이론

 

📍문제 풀이

- 9655번 돌게임과 비슷한데, 이번엔 4개를 가져갈 수도 있음

- 따라서 선택지가 3개 (1, 3, 4)

 

그래서.. 기존처럼 양분되는 것이 아니기 때문에, 새로운 필터링 조건이 필요

 

상근이가 먼저 게임을 시작하니까 상근이 입장에서 풀이

 

어떤 수 N에서 바로 이길 수 있으면 1, 다음 사람이 이기면 0을 할당

예) N = 1, 3, 4 이면 상근이가 바로 이기므로 1

N = 2 이면 창영이가 이기므로 0

 

돌게임 1, 2에서는 홀수/짝수에 따라 이기는 사람이 정해져 있었지만, 돌게임 3에서는 확신할 수 없음

선택지가 3개이므로 Math.min으로 판별 불가

 

따라서 이렇게 생각하기

N = 5 일 때

-1 => 4 (1)

-3 => 2 (0) -> 한 번이라도 0이 있으면? 다음 다음인 자신(상근)이 이기므로 1

-4 => 1 (1)

⭐설정할 조건 : 3가지 경우를  더해서 3보다 작은 경우 => 하나라도 0

⭐반면 전부 1이면? 한번 다음 스텝으로 넘어갔는데 전부 바로 이기는 것이므로 창영이가 이기는 것

 

📍코드 (JavaScript)

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const N = +input;

const dp = (num) => {
  const memo = [0, 1, 0, 1, 1];

  for (let i = 5; i <= num; i++) {
    // 하나라도 0이면 다음에 상근이가 이기는 거니까 1
    if (memo[i - 1] + memo[i - 3] + memo[i - 4] < 3) memo[i] = 1;
    // 전부 1이면 무조건 횟수 2번이므로 창영이가 이김. 따라서 0
    else memo[i] = 0;
  }

  return memo[num] === 1 ? "SK" : "CY";
};

console.log(dp(N));