[백준][C++] 9655번 돌 게임

돌 게임

문제 링크

돌 게임

분석

입력으로 돌의 개수를 의미하는 정수 N이 주어집니다.

돌은 한 번에 1개 또는 3개만 가져갈 수 있으므로, 작은 경우를 직접 확인해보면 다음과 같습니다.

1. 돌이 1개일 때
   • 상근1
2. 돌이 2개일 때
   • 상근1, 창영1
3. 돌이 3개일 때
   • 상근3
4. 돌이 4개일 때
   • 상근3, 창영1
   • 상근1, 창영3
5. 돌이 5개일 때
   • 상근3, 창영1, 상근1
   • 상근1, 창영3, 상근1
   • 상근1, 창영1, 상근3
6. 돌이 6개일 때
   • 상근3, 창영3
   • 상근1, 창영3, 상근1, 창영1
   • 상근1, 창영1, 상근3, 창영1
   • 상근1, 창영1, 상근1, 창영3

이를 통해 돌의 개수가 홀수일 때는 상근이가 이기고, 짝수일 때는 창영이가 이긴다는 규칙을 찾을 수 있습니다.

또 다른 방법으로 보면, 한번에 가져갈 수 있는 돌의 개수는 1개 또는 3개인데 둘 다 홀수입니다.
즉, 한 번 돌을 가져갈 때마다 남은 돌의 개수의 홀짝성은 항상 바뀌게 됩니다.

홀수와 짝수로 구분한다면 다음과 같습니다.

처음 N이 홀수일 경우 상근이가 돌을 가져간 뒤 남은 돌은 짝수, 창영이가 가져가면 다시 홀수가 됩니다.
이 과정이 반복되면 마지막 돌은 상근이가 가져갑니다.

처음 N이 짝수일 경우 상근이가 가져간 뒤 남은 돌은 홀수, 창영이가 가져가면 다시 짝수가 됩니다.
이 과정이 반복되면 마지막 돌은 창영이가 가져갑니다.

따라서 N이 홀수라면 상근이가 가져가고, 짝수라면 창영이가 가져가게 됩니다.

풀이

#include <iostream>

using namespace std;

int main()
{
	int n;
	
	cin >> n;

	if (n % 2 == 0)
	{
		cout << "CY";

	}
	else
	{
		cout << "SK";
	}

	return 0;
}

성능 요약

시간 복잡도는 상수 시간에 끝나기 때문에 $O(1)$입니다.

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

메모리: 2020 KB

시간: 4 ms