📍유사 문제
2023.01.13 - [⚙️알고리즘 & 자료구조/BOJ] - 백준 9655 < 돌 게임 > JavaScript
📍문제 링크
https://www.acmicpc.net/problem/9657
📍알고리즘 분류
- 다이나믹 프로그래밍
- 게임 이론
📍문제 풀이
- 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));