[Baekjoon] 돌 게임

👀 문제 설명

문제

돌 게임은 두 명이서 즐기는 재밌는 게임이다.

탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.

두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.

 

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000)

 

출력

상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다.

 

예제 입력 1

5

 

예제 출력 1

SK

 

✍🏻풀이

나는 직접 게임을 돌려보고, 규칙을 찾았는데 홀수일 때는 상근이가, 짝수일 때는 창영이가 번갈아가면서 이기는 것이었다.

번갈아가면서 이기는거라 i가 N까지 dp[i] = !dp[i -1] 이렇게 넣어줬는데 생각해보니까 그냥 N이 홀수일 때는 SK를 출력하고, 짝수일 때는 CY를 출력하면 된다..^^

 

그리고 다른 풀이를 찾아보니까, 게임의 룰이 홀수개만 가져갈 수 있는 룰이기 때문에 여기서 규칙을 얻을 수 있다.

홀수 + 홀수 = 짝수

홀수 + 짝수 = 홀수 + 홀수 + 홀수 = 홀수

이고, 상근이가 먼저 시작하므로, 홀수일 때는 상근이가, 짝수일 때는 창영이가 이기는 규칙을 찾을 수 있다.

 

코드

정답1 (내가 푼 풀이)

//  돌 게임 (https://www.acmicpc.net/problem/9655)

#include <iostream>

#define MAX 1001

using namespace std;

int dp[MAX]; // 상근이가 이길 경우 1, 질 경우 0

int main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);

    int N;
    cin >> N;

    dp[1] = 1; dp[2] = 0; dp[3] = 1;
    for (int i = 4; i <= N; i++) {
        dp[i] = !dp[i - 1];
    }

    cout << (dp[N] ? "SK" : "CY") << "\n";

    return 0;
}

 

정답2 (쉬운 풀이)

//  돌 게임 (https://www.acmicpc.net/problem/9655)

#include <iostream>

#define MAX 1001

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);

    int N;
    cin >> N;

    cout << ((N % 2 == 1) ? "SK" : "CY") << "\n";

    return 0;
}