[백준] 9657번. 돌 게임 3
1. 문제
돌 게임은 두 명이서 즐기는 재밌는 게임이다.
탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개, 3개 또는 4개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.
두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.
2. 입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000)
3. 출력
상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다.
4. 풀이
DP문제- 완벽한 게임을 하기 때문에 역으로 추적 해보면 된다.
- 현재 돌의 개수에서 1개, 3개, 4개를 뺐을 때 내가 이길 수 있는 경우가 있는지 확인하면 된다.
- 돌이 1개일 때는 시작하는 사람
(상근)이 이긴다. - 돌이 2개일 때는 상근이가 하나밖에 가져갈 수 없기 때문에 1개가 남는 사람
(창영)이 이긴다. - 돌이 3개일 때는 시작하는 사람
(상근)이 이긴다. - 돌이 4개일 때는 시작하는 사람
(상근)이 이긴다. - 돌이 5개일 때는 1개, 4개를 가져가면 시작하는 사람이 지고 3개를 가져가면 시작하는 사람이 이긴다. 완벽한 게임이기 때문에 시작하는 사람이 이긴다고 봐야한다.
if(arr[i-1] && arr[i-3] && arr[i-4]) arr[i] = false;
else arr[i] = true;
5. 처음 코드와 달라진 점
null
6. 코드
#include <iostream>
#include <algorithm>
using namespace std;
bool arr[1001];
int main(){
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int n;
cin>>n;
arr[1] = true;
arr[2] = false;
arr[3] = true;
arr[4] = true;
for(int i=5; i<=n; ++i) {
if(arr[i-1] && arr[i-3] && arr[i-4]) arr[i] = false;
else arr[i] = true;
}
if(arr[n]) cout<<"SK";
else cout<<"CY";
}
