Node.js) 백준 9658번: 돌 게임 2

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

9658번: 돌 게임 4

 

 

dp[i] 는 돌이 i 개 있을 때, 완벽하게 게임을 했을 때, 게임의 승자

dp[i] 가 true 면 상근이 승리
dp[i] 가 false 면 창영이 승리

조건식
dp[i] = !dp[i-1] || !dp[i-3] || !dp[i-4]

초기값
dp[1] = false(CY)
∵ sk1 => cy win

dp[2] = true(SK)  
∵ sk1-cy1 => sk win

dp[3] = flase(CY)
∵ sk1-cy1-sk1 => cy win
∵ sk3 => cy win

dp[4] = true(SK)
∵ sk4 => cy win
∵ sk3 cy1 => sk win

 

const input = +require('fs').readFileSync('./dev/stdin').toString().trim();
const s = true;
const c = false;
let dp = []; // 이긴사람
dp[1] = c;
dp[2] = s;
dp[3] = c;
dp[4] = s;

for (let i = 5; i <= input; i++) {
	dp[i] = !dp[i - 1] || !dp[i - 3] || !dp[i - 4];
}

console.log(dp[input] ? 'SK' : 'CY');