백준 9655 < 돌 게임 > JavaScript

📍문제 링크

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

9655번: 돌 게임

 

📍알고리즘 분류

- 수학

- 다이나믹 프로그래밍

- 게임이론

 

📍문제 풀이

두 사람 A, B가 게임을 하는데 N개의 돌 중에 1, 3개를 택해서 가져갈 수 있다. 마지막에 가져가는 사람이 이긴다.

두 사람이 완벽하게 게임을 했을 때, 이기는 사람은 누구일까?

 

🤔완벽하게 게임을 했을 때?

- 이길 수 있는 상황에서 게임을 이기는 것. 확실한 finish로 시행 횟수를 최소화 하는 것!

- 예) N = 7, A, B가 플레이어

A B A

1 3 3(무조건 3을 냄, 1을 내지 않음)

 

 

일단 A가 이긴다는 것은 진행 횟수가 홀수번

B가 이긴다는 것은 진행 횟수가 짝수번이라는 것을 알 수 있다!

 

⭐모르겠을 땐, N = 1 부터 경우의 수 세어보기

N = 1

A(승)

1

 

N = 2

A B(승)

1 1

 

N = 3

A(승)

3

 

N = 4 (여기 부턴 경우의 수가 나뉨)

i)

A B(승)

1 3

 

ii)

A B(승)

3 1

 

N = 5

i)

A B A(승)

1 1 3

 

ii)

A B A(승)

1 3 1

 

iii)

A B A(승)

3 1 1

 

N = 홀수 => A 승

N = 짝수 => B 승

 

하지만, DP로 풀어봐야 한다!

⭐DP의 핵심은 N이 늘어날 수록 이전 값을 활용할 수 있는지(memoization) 따져보면 된다

/*
N = 5 = DP[5]

A
              -> 3 (DP[1] + 2) -> 1 (DP[0] + 3)
1 (DP[4] + 1) 
              -> 1 (DP[3] + 2) -> 3 (DP[0] + 3)
              
              
3 (DP[2] + 1) -> 1 (DP[1] + 2) -> 1 (DP[0] + 3)
 */

 

돌을 1개 혹은 3개 가져가면, 다음차례에서는 횟수가 1 증가하고 새롭게 N - n 개의 돌에서 새 게임을 하는 경우를 세면 된다

 

N = 3 까지 memo 배열을 미리 만들어 둘 수 있다

memo = [0, 1, 2, 3]

 

따라서 점화식을 아래처럼 세울 수 있다

DP[N] = min(DP[N - 1] + 1, DP[N - 3] + 1)

 

📍코드 (JavaScript)

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

const N = +n;

const dp = (num) => {
  if (num === 1) return "SK";
  if (num === 2) return "CY";
  if (num === 3) return "SK";
  const memo = [0, 1, 2, 1];
  for (let i = 4; i <= num; i++) {
    memo[i] = Math.min(memo[i - 1] + 1, memo[i - 3] + 1);
  }
  return memo[num] % 2 === 0 ? "CY" : "SK";
};

console.log(dp(N));