Node.js) 백준 9657번: 돌 게임3

 

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

9657번: 돌 게임 3

 

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

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

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

dp[i-1] 은 돌이 i-1 개 있을 때 마지막으로 돌을 가져간 사람.
그리고 1개를 다음 사람이 가져가고, 그사람이 이기게 됨. => !dp[i-1]

1,3,4 세가지 경우를 고려하여 셋 중 하나라도 상근이가 이길 수 있는 경우가 있다면.
상근은 해당 경우를 선택.

초기값
dp[1] = true(SK)
dp[2] = false(CY)
dp[3] = true(SK)
dp[4] = true(SK)

 

 

const input = +require('fs').readFileSync('./dev/stdin').toString().trim();

const SK = true;
const CY = false;

let dp = [];
dp[1] = SK;
dp[2] = CY;
dp[3] = SK;
dp[4] = SK;
for (let i = 5; i <= 1000; i++) {
	dp[i] = !dp[i - 1] || !dp[i - 3] || !dp[i - 4];
}
console.log(dp[input] ? 'SK' : 'CY');