[알고리즘] 돌 게임 6

구현 방식

• 돌 개수가 1억은 가뿐히 넘겨버려서, O(N) 으로 풀어도 안된다.
• 일단 돌 개수에 따라 승패가 어떻게 바뀌는지 확인해보자.
• 아래의 사진처럼 승패가 갈리는데, 약간의 규칙이 있다.
• win[k] = ANY(X == "CY", "SK", "CY") , X = win[k-1] , win[k-3] , win[k-4] 이다.
• 즉, win[k] 는 win[k-1] , win[k-3] , win[k-4] 중에 "CY" 가 하나라도 나온다면 "SK" 이고 아니라면 "CY" 이다.
• 왜냐하면, 상근이가 돌을 1, 3, 4 가져간다면 그 이후에는 창영이가 감소된 돌의 개수로 게임을 처음 시작하는것과 같은 결과를 낳기 때문이다. 그래서, 상근이가 돌을 1, 3, 4 가져가는 경우의 수중에서 "CY" 가 나오는 경우를 고른다면 상근이가 이기게된다.

• 이렇게 해서 문제를 푼다고해도,,, 10^12이기 때문에 메모리 초과가 난다.
• 위에서 작성한 표를 확인하면, 더 간단한 규칙이 보인다. 7로 나누었을 때 나머지 2 또는 0 이면 "CY" 가 이기게 된다는 것을 ..!

코드

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

void solution(long long N)
{
	int remained = N % 7;
	if (remained == 0 || remained == 2)
		cout << "CY";
	else
		cout << "SK";
}