[ 백준 ] 9657 / 돌 게임 3

金弘均·2021년 9월 16일
0

Baekjoon Online Judge

목록 보기
185/228
post-thumbnail

# Appreciation

/*
 * Problem :: 9657 / 돌 게임 3
 *
 * Kind :: Dynamic Programming
 *
 * Insight
 * - 돌이 2개가 남았다면
 *   상근이는 질 수밖에 없다
 *   + 상근 1개 => 창영 1개
 *     # 그렇다면 돌이 6개 남았다면 어떻게 될까?
 *       -> 상근 4개 => 창영 1개 => 상근 1개
 *          상근이가 이기게 된다
 *
 * - Case 1.
 *   돌이 N 개 남았을 때
 *   상근이가 질 수 밖에 없다면
 *   + 돌이 N+1개, N+3개, N+4개 남았을 때는
 *     상근이가 이기게 된다
 *
 * - Case 2.
 *   돌이 N 개 남았을 때
 *   + 돌이 N-1개, N-3개, N-4개 남았을 때
 *     상근이가 질 수밖에 없는 경우가 있으면
 *     N개 남았을 때는 상근이가 이기게 된다
 *
 * Point
 * - Case 1. 처럼
 *   + dp[i] == LOSE 일 때,
 *     dp[i+1, i+3, i+4] = WIN 으로 구현한 것과
 *   Case 2. 처럼
 *   + dp[i-1, i-3, i-4] 중 하나라도 LOSE 이면
 *     dp[i] = WIN 으로 구현한 것은
 *     # 현 상태로부터 다음 상태를 정하는 것과
 *       이전 상태로부터 현 상태를 정하는 것의 차이일 뿐
 *       논리는 같다!
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <cstring>

using namespace std;

#define endl '\n'

// Set up : Global Variables
#define WIN true
#define LOSE false

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N; cin >> N;

    // Process
    bool dp[N+1]; /* dp[i] = 돌이 i개 남았을 때 상근이가 이기면 WIN(true)
                   *         그렇지 않으면 LOSE(false) */
    memset(dp, LOSE, sizeof(dp));
    dp[1] = dp[3] = dp[4] = WIN;

    /* 현 상태로부터 다음 상태를 결정 */
    for (int i=1; i<=N; i++) {
        if (dp[i] == LOSE) {
            if (i+1 <= N) { dp[i+1] = WIN; }
            if (i+3 <= N) { dp[i+3] = WIN; }
            if (i+4 <= N) { dp[i+4] = WIN; }
        }
    }

    /* 이전 상태로부터 현 상태를 결정 */
//    for (int i=5; i<=N; i++) {
//        if (dp[i-1] == LOSE || dp[i-3] == LOSE || dp[i-4] == LOSE) {
//            dp[i] = WIN;
//        }
//    }

    // Control : Output
    cout << ((dp[N] == WIN) ? "SK " : "CY") << endl;
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글