[알고리즘] 돌 게임

구현 방식

• 백준 문제 분류에 “게임 이론” 아리는게 있길래 확인 해봤더니 이런게 있구나,, 신기하다.
• 서로가 최대한 이기기 위해서 게임 규칙을 수행한다.
• 이기게 하기 위해서는 다음과 같이 생각했다.
  • 돌 개수가 1 또는 3 개 이면 모두 가져가기
  • 돌 개수가 6 보다 작으면, 3개를 가져가면 이후에 상대방이 3개를 가져가게 되어버리면 지게되므로, 1개만 가져간다.

코드

• 최종 코드는 아래와 같다.

void solution(int N)
{
	while (true)
	{
		N = getStone(N);
		if (N <= 0)
		{
			cout << "SK";
			return;
		}
		N = getStone(N);
		if (N <= 0)
		{
			cout << "CY";
			return;
		}
	}
}


int getStone(int remained)
{
	if (remained == 3 || remained == 1)
		return 0;
	if (remained <= 6)
		return remained - 1;
	else
		return remained - 3;
}