[백준] 9656번. 돌 게임2
하스스톤
1. 문제
돌 게임은 두 명이서 즐기는 재밌는 게임이다.
탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 지게 된다.
두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.
2. 입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000)
3. 출력
상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다.
4. 풀이
DP로 풀었다.
머리가 안 돌아가서 죽는 줄 알았다.- 항상 최선의 선택을 한다고 했으니
1개혹은3개중에서 내가 이길 수 있는 경우를 가져온다. - 1부터 차례대로
index를 증가시키면서 탐색했다. - 1개일 때는 무조건 1개를 가져와야 한다. 그래서 상근이가 진다.
- 2개일 때는
1개혹은3개를 가져올 수 있는데 3개를 가져오면 마지막 돌은 가져온 것이라 상근이가 진다. 반면 1개를 가져오면 창영이게게 1개를 줄 수 있기 때문에 상근이가 이긴다. - 3개일 때는
1개혹은3개를 가져올 수 있는데 3개를 가져오면 마지막 돌도 가져온거라 진다. 그리고 1개를 가져오면 2개가 남는다. 아까 2개가 남으면 무조건 2개가 남았을 때 선택권 있는 사람이 이기는 걸 확인했다(여기서 DP가 쓰인다.). 3개일 때는 선택권을 가진 사람(상근)이 무조건 진다. - 4개일 때는 1개와 3개를 남길 수 있다. 1개를 남기든 3개를 남기든 선택권을 가진 사람이 진다. 즉, 4개 일 때는 선택권을 가진 사람이 무조건 이긴다.
boolean배열에 위의 정보를 저장한다. 1개 가져오기와 3개 가져오기 중 이길 수 있는 경우가 하나라도 있다면 선택권을 가진 사람이 이긴다. 반면, 둘 다false면(=둘 다 선택권을 가진 사람이 지면) 해당 개수의 돌을 가진 사람은 무조건 진다.
5. 처음 코드와 달라진 점
- 둘 중 하나라도 false 면이라는 조건은
!A || !B인데 저걸 묶고 싶어서(A&&B)로 묵었다. 멍청스...!(A&&B)가 맞음
6. 코드
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
bool arr[1001];
arr[1] = false;
arr[2] = true;
arr[3] = false;
int n;
cin >> n;
for (int i = 4; i <= n; i++) {
if (!(arr[i - 1] && arr[i - 3])) arr[i] = true;
else arr[i] = false;
}
if (arr[n]) cout << "SK";
else cout << "CY";
}