백준 9655번 / S5 / C++

문제주소 : https://www.acmicpc.net/problem/9655
문제이름 : 돌 게임
문제번호 :9655
난이도 : S5

소요시간 : 7m 8s

 

돌 게임 성공

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

41560

27219

22913

66.370%

문제

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

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

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

입력

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

출력

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

예제 입력 1 

5

예제 출력 1 

SK

 

풀이

이 게임에서 승리하려면 마지막 내 차례에 남은 돌이 1개 또는 3개여야한다.

상대로 하여금 1 또는 3으로만 만들 수 있게 하는 수는 4이다.

즉 상대에게 4를 강제시키면 된다.

이 게임은 순서대로 진행하여 항상 턴마다 4개를 뺄 수 있다.

즉 내가 먼저 4n의 값을 만들면 상대에게 4라는 숫자를 남겨 줄 수 있는 것이다.

#include <iostream>
using namespace std;
int main() {
	//상대한테 4개가 남아야함
	//항상 4n을 만들수 있다면 승리
	//처음이 9다? 1빼준다
	//상대가 8에서 3을 빼건 1을 빼건
	//7,5에서 4n을 유지 가능함
	//만약 10이라면? 9 또는 7로 만드는데 이경우 상대가 먼저 4n을 만든다.
	//즉 1또는 3을빼서 4n이 된다면 상근 아니라면 창영이 승리다.

	int n;
	cin >> n;
	
	if ((n - 1) % 4 == 0 || (n - 3) % 4 == 0) {
		cout << "SK";
	}
	else {
		cout << "CY";
	}
}