[백준/BOJ] 9655번: 돌 게임 (C++)

문제

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

 

문제 이해

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

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

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

​

입력과 출력

입력

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

출력

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

 

풀이

상근이와 창영이가 게임을 했을 때의 상황을 표로 정리해봤다.

`dp[N]`은 돌을 가져간 횟수이다.

N	게임 순서	`dp[N]`	이긴 사람
1	1	1	상근
2	1 → 1	2	창영
3	3	1	상근
4	1 → 3 또는 3 → 1	2	창영
5	1 → 3 → 1 또는 1 → 1 → 3 또는 3 → 1 → 1	3	상근
6	3 → 3	2	창영
⁝	⁝	⁝	⁝

 

이 게임은 `N`이 홀수면 상근이가, 짝수면 창영이가 이기는 게임이다.

`N` 값에 따라 SK나 CY를 출력해도 되지만 dp를 연습하기 위해서 dp 배열을 선언해서 코드를 작성했다.

`dp[i]`는 전 차례에서 3개를 가져갔을 때(`dp[i-3]`)와 1개를 가져갔을 때(`dp[i-1]`)의 플레이 횟수의 최솟값에 1을 더해서 구해주었다.

그리고 `dp[i]`가 홀수면 SK, 짝수면 CY를 출력하도록 했다.

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

int N;
int dp[1001];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;

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

    if (dp[N] % 2) {
        cout << "SK";
    }
    else {
        cout << "CY";
    }
    return 0;
}