Baekjoon 9658: 돌 게임 4
- 최초 작성일: 2021년 9월 21일(화)
- 주소: https://www.acmicpc.net/problem/9658
목차
[TOC]
문제 설명
- 돌 게임은 두 명이서 즐기는 재밌는 게임이다.
- 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개, 3개 또는 4개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 지게 된다.
- 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.
입력
- 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000)
출력
-
상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다.
알고리즘 분류
- 다이나믹 프로그래밍
- 게임 이론
풀이 방법
- 이 문제는 두 명이서 최선의 플레이를 했을 때, 승자가 누구인지 맞추는 문제이다. 이때 마지막 돌을 가져가는 사람이 패자이다.
- 한번에 1개, 3개 또는 4개를 가져갈 수 있다고 했기 때문에, 만약 SK가 2개를 가져갔다면, 여기서 CY는 주어지는 돌의 수가 2+1개, 2+3개 또는 2+4개일 때 무조건 승자가 된다.
- 그러므로 주어진 돌의 수가 6개라면 6-1개, 6-3개 또는 6-4개에서의 승자가 6개에서는 패자가 된다.
- 일단 우선, 1~4개일 때는 4-4=0개가 되기 때문에, 임의로 승자를 지정해주었다.
- SK가 승자라면 1, CY가 승자라면 0을 넣어주었다.
- SK가 먼저 게임을 시작한다고 했으니, 두 명이 최선의 플레이를 할 때, 아래의 순서대로 돌을 가져가게 될 것이다. 그래서 아래와 같이 임의로 값을 지정해주었다.
- 돌 1개: SK 1개 -> CY 승 (0)
- 돌 2개: SK 1개 + CY 1개 -> SK 승 (1)
- 돌 3개: SK 1개 + CY 1개 + SK 1개 -> CY 승 (0)
- 돌 4개: SK 1개 + CY 1개 + SK 1개 + CY 1개 / SK 3개 + CY 1개 -> SK 승 (1)
- 돌 5개부터는 dp를 사용해서 구해낼 수 있다. (모두 1일 때만 0이 된다 -> CY가 승리)
- 돌 5개: dp[5-1]=1, dp[5-3]=1, dp[5-4]=0 » dp[5] == 1 (SK 승)
- 돌 6개: dp[6-1]=1, dp[6-3]=0, dp[6-4]=1 » dp[6] == 1 (SK 승)
- 위의 법칙을 구체적으로 설명하자면, 승자 혹은 패자가 생기는 방법은 여러가지가 있다. 마지막 플레이어가 1개를 가져가면서 패배할 수도 있고, 3개 혹은 4개를 가져가면서 패배할 수 있기 때문에, 현재 갯수에서 -1, -3, -4번째의 돌에서의 패자가 현재 갯수에서의 승자가 된다.
- 위의 법칙을 dp 방법으로 반복해나가면 된다.
#include <iostream>
#include <algorithm>
using namespace std;
// 백준 9658번: 돌 게임 4
int dp[1001];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int DP[1010];
int n; cin >> n;
DP[1] = 0;
DP[2] = 1;
DP[3] = 0;
DP[4] = 1;
for (int i = 5; i <= n; ++i) {
if (min({ DP[i - 1], DP[i - 3], DP[i - 4] }) == 1) DP[i] = 0;
else DP[i] = 1;
}
if (DP[n] ==1) cout << "SK" <<"\n";
else cout << "CY" <<"\n";
return 0;
}