[Node.js] 백준 9657 - 돌 게임3

이런 게임 이제 그만

접근

필승 전략이 있는지 판단해서 풀기로 했다.

이전에 돌 게임을 풀었던 기억과, 짧은 인풋 -> DP 로 풀어야겠다는 생각.

돌이 i개 있을 때 현재 플레이어 or 상대방 누가 이기는지 판단하면 되는 간단(?)한 문제.

핵심!

내가 이기려면 상대방을 “패배시킬 수 있는 방법(false로 지정함)”이 있어야 한다.

즉 이전 과정에서 하나라도 F가 존재해야, 내가 이길 수 있다.

하지만 TTT 즉 상대방이 전부 이기는 수로 넘겨주면, F

구현 및 정답코드

const fs = require('fs');
const INPUT_PATH = 0; 
const input = fs.readFileSync(INPUT_PATH, 'utf8').trim();
const N = Number(input);

/**
 * @param {number} N
 * @description N을 입력받아 상근이와 창영이 중 누가 이기는지 판단한다.
 * DP[i]: 돌이 i개 남았을 때 현재 플레이어의 승리 여부 (True: 승리 가능)
 */
function solution(N) {
    // DP 배열은 N+1 크기로 생성
    const dp = new Array(N + 1);

    // 초기값 설정
    // N=1: SK 승리 (T)
    dp[1] = true;
    // N=2: SK가 1개 가져가면 DP[1]=T 상태를 CY에게 넘겨줌. CY 승리 (F)
    dp[2] = false; 
    // N=3: SK가 3개 가져가면 이김 (T)
    dp[3] = true; 
    // N=4: SK가 4개 가져가면 이김 (T)
    dp[4] = true;

    // N이 4 이하일 경우 미리 리턴
    if (N <= 4) {
        return dp[N] ? "SK" : "CY";
    }

    // DP 점화식 계산 (i=5부터 N까지)
    for (let i = 5; i <= N; i++) {
        // take_k: k개를 가져갔을 때, 상대방이 이기는가? (dp[i-k]의 값)
        const take1 = dp[i - 1]; 
        const take3 = dp[i - 3];
        const take4 = dp[i - 4];

        // 현재 플레이어의 승리 조건: !(모두 True)
        // (하나라도 False 상태로 상대를 몰아넣을 수 있는 경우가 있는가?)
        dp[i] = !(take1 && take3 && take4);
    }

    // 최종 결과 출력 (dp[N]이 true면 상근이(SK) 승리)
    return dp[N] ? "SK" : "CY";
}

console.log(solution(N));

후기

아.

12시 전에 냈는데…

채점이 이리 오래 걸릴줄이야…

앗..아아.. 라고 생각했는데 살아남은 나의 초록색 작고 귀여운 잔디.

잔디라기엔 구멍이 많지만, 열심히 하다보면 괜찮을거야~