백준 9655번 돌 게임

🔒[문제 url]

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

🪄전체 코드

#include <iostream>
#include <string>
using namespace std;

int n;

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
}


void SOLVE()
{
    /*
    돌의 갯수가 1 or 3인 경우 상근이가, 2인 경우 창용이가 이김을 알 수 있다.
    또한, i개의 돌이 남아있을 때의 게임 횟수는 (i-1)개 or (i-3)개가 남아있을 때의
    게임 횟수 중 최솟값에 1을 더한 값임을 알 수 있다.
    이에 기반하여 dp[0]을 시작으로 표를 작성하면,
    0 1 2 1 2 3 2 3 4 3 4 5 4 ----- 형태로 반복됨을 알 수 있고,
    상근이가 먼저 돌을 가져가므로, 게임 횟수가 홀수일 때 상근이가 승리하게 된다.
    따라서 dp[n]의 값이 홀수이면 SK를, 짝수면 CY를 출력하면 된다.
    
    + 이를 한번 더 최적화하여, n이 홀수이면 dp[n]이 홀수,n이 짝수라면 dp[n]또한 짝수임을 알 수 있다.
    따라서 n의 홀짝을 판단하여 답안을 출력할 수 있다.
    */
    
    if (n % 2 == 0)
		cout << "CY";
	else cout << "SK";
    
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

GOLD5 미만 난이도는 알고리즘 및 풀이 설명을 주석으로 대체합니다.
주석을 참고해주세요.