[ 백준 ] 9659 / 돌 게임 5

金弘均·2021년 9월 16일
0

Baekjoon Online Judge

목록 보기
193/228
post-thumbnail

# Appreciation

/*
 * Problem :: 9659 / 돌 게임
 *
 * Kind :: Math
 *
 * Insight
 * - 보통 다른 돌 게임 문제라면 DP 로 풀었겠지만...
 *   max(N)=10^12 니 시간초과가 날 수밖에 없다...
 *   + 하지만, 언제나 그렇듯 우리는 풀어내어야 한다
 *
 *
 * - 다른 돌 게임 문제와 푸는 논리는 같다
 *   + 돌이 n 개 남았을 때, 상근이가 이긴다면
 *     돌이 n+1, n+3 개 남았을 때는 상근이가 진다 => 창영이가 이긴다
 *   + 돌이 n 개 남았을 때, 창영이가 이긴다면
 *     돌이 n+1, n+3 개 남았을 때는 창영이가 진다 => 상근이가 이긴다
 *
 * - 돌이 남은 개수 | 누가 이기는가
 *   + 돌을 1개 또는 3개 가져갈 수 있으므로
 *     1 | SK
 *     2 | CY
 *     3 | SK
 *     는 자명하다
 *     # 4 | CY (1+3, 3+1)
 *       5 | SK (2+3, 4+1)
 *       6 | CY (3+3, 5+1)
 *       ...
 *       -> 홀수면 SK, 짝수면 CY
 *       
 * Point
 * - DP 가 아닌 규칙으로 푸는 문제가 있겠지 싶었는데
 *   역시 있었네 ㅋㅋ
 *   + 이제 돌 1, 3, 4 개 가져갈 수 있는
 *     변형된 문제도 있겠군 ㅎㅎ
 */

# Code

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

#include <iostream>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

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


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

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

    // Control : Output
    cout << ((N%2) ? "SK" : "CY") << endl;
}

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

0개의 댓글