[BOJ][백준] 2373번: Fibonacci Game

https://www.acmicpc.net/problem/2373

2373번: Fibonacci Game

 

문제

당신은 N(2≤N≤1,000,000) 개의 구슬을 가지고 다음과 같은 게임을 하려고 한다. 게임은 두 사람이 번갈아 가면서 진행하며, 1번 사람이 몇 개의 구슬을 가져가는 것으로 게임이 시작된다. 1번 사람이 처음에 구슬을 가져갈 때는 몇 개라도 가져갈 수 있지만 N개의 구슬을 다 가져가서는 안 된다. 그 후에 구슬을 가져갈 때는, 상대편이 바로 전에 가져간 개수의 2배 이하를 가져갈 수 있다. 즉, 상대편이 1개를 가져갔다면, 당신은 1개, 또는 2개를 가져갈 수 있는 것이다. 이런 식으로 게임을 진행하여, 마지막으로 구슬을 가져간 사람이 이기게 된다.

예를 들어, N=3인 경우를 보자. 1번 사람이 몇 개를 가져가도 2번 사람이 남아있는 구슬을 다 가져갈 수 있다. 반면에 N=4인 경우에는, 1번 사람이 1개를 가져가면 이기게 된다.

1번 사람의 입장이 되어, 처음에 몇 개의 구슬을 가져갈 것인지를 결정하는 프로그램을 작성하시오. 만약 가능한 경우가 여러 가지 존재한다면, 더 적은 수의 구슬을 가져가는 것으로 한다. 만약 몇 개를 가져가도 지게 된다면, -1을 출력한다.

입력

첫째 줄에 정수 N이 주어진다.

출력

가져갈 구슬의 개수, 또는 -1을 출력한다.

 

---

 

오랜만의 포스팅입니다. 최근 카카오 인턴코테글의 조회수가 엄청났었는데, 어제부터 떡락해서 확인해보니 이번 여름 인턴 코테가 토요일이었네요ㅋㅋㅋㅋㅋ 요즘 포스팅이 없었던 이유는, 여러 새로운 알고리즘을 공부하느라 시간이 안 나서인데, 그 새로운 알고리즘 중 하나가 오늘 포스팅의 주제인 스프라그-그런디 정리입니다. 이 이론은 게임 이론 문제를 풀 때 사용하게 되는 알고리즘인데, 제가 글을 쓰기엔 난도가 높고 매우 길어질 거 같아서.. 혹시 공부하실 생각이 있으신 분들은 다음 링크를 참조해주세요. 절대 입문용은 아니고, DP 및 수학 전반적으로 깊은 이해가 요구됩니다.

이 문제는 적당히 100이하의 값들에 대한 그런디 수를 구한 후, 그 패턴의 규칙을 찾아 1백만 정도의 수까지의 n에 대한 답을 도출해야 합니다. 그런디 수를 찾는 함수를 찾는 것은 어렵지 않습니다. 

int f(int now, int last)
{
	if (now == 0)return 0;

	int&ret = cache[now][min(now, last)];
	if (ret != -1)return ret;
	bool visited[101] = { 0, };

	for (int i = 1; i <= min(now, last * 2); i++)
		visited[f(now - i, i)] = true;

	for (int i = 0; i<101; i++)if (!visited[i])return ret = i;

}

int ans(int now)
{
	for (int i = 1; i<now; i++)
		if (f(now - i, i) == 0)return i;
	return -1;
}

그런디 수를 구하는 f함수 가있고, 1번 사람의 입장이 되어, 처음에 몇 개의 구슬을 가져갈 것인지를 결정해야 하기 때문에 ans함수도 작성해 주었습니다. 그럼 2부터 30까지의 답을 출력해 볼까요?

(1)

무슨 규칙이 보이시나요? 잘 안 보여도 좋습니다. 규칙은 반드시 존재하고, 우리는 충분히 찾을 수 있으니까요. -1의 빈도 간격에서 뭔가 규칙이 있는 것도 같습니다. -1의 간격이 0,1,2,4,7... 이래서는 규칙이 안 보이네요. 조금 다르게 정렬을 해 볼까요? 

(2)

이제 뭔가 규칙이 보이는 것 같습니다. 직관적으로 보이는 건 피보나치수는 ans값이 -1이라는 점이 돋보입니다. 그러고 보니 이문제의 제목이 뭐였죠? Fibonacci Game입니다. 제목에 힌트가 숨어져 있었네요. 피보나치 수라는 건 알았는데, 그럼 피보나치 수 사이의 저 {1,2,3,1,5,1,2,8,1,2,3,1,13,1,2,3... } 배열은 무슨 규칙이 있는 걸까요?

위의 배열에도 뭔지는 몰라도 피보나치 수가 관련되어있다는 사실은 금방 눈치챌 수 있습니다. 더 직관적으로 저 배열을 관찰 해 봅시다.

{1,2,3,1,5,1,2,8,1,2,3,1,13,1,2,3... } 피보나치 수 사이의 수들은 재귀적으로 서로 연결되어 있습니다. 뭔가 규칙이 보이긴 보이는데, 이걸 어떻게 코드로 써 내려갈까요? 우선 저 배열을 Zec배열이라고 선언을 해봅시다.(변수명이 Zec인 이유는 밑에 나옵니다.) 우선 피보나치 수는 자기 인덱스 값에 들어가게 만듭니다. Zec [1]=1, Zec [2]=2, Zec [3]=3, Zec [5]=5... 이런 식으로 말이죠. 그다음 피보나치 수가 아닌 수의 Zec값은 다음으로 정의됩니다.

{n| n보다 작은 가장 큰 피보나치수를 i라 했을 때, Zec [n]=Zec [n-i]}

n=4일 때, 4보다 작은 가장 큰 피보나치 수는 3이므로 Zec [4]=Zec [1]=1이 됩니다. n=12일 때, 12보다 작은 가장 큰 피보나치수는 8이므로 Zec [12]=Zec [4]=1 가 됩니다. 다행히 N의 제한이 1백만이므로 Zec배열을 모두 선언해서 시간 복잡도  O(N)으로 모든 Zec배열을 구할 수 있습니다. 

const int MAX_N = 1000001;
int Zec[MAX_N];
vector<int>fibo;

void getZec()
{
	memset(Zec, 0, sizeof(Zec));
	int fib1 = 1, fib2 = 2;
	while (true)
	{
		fibo.push_back(fib1);
		Zec[fib1] = fib1, Zec[fib2] = fib2;
		int next1 = fib2, next2 = fib1 + fib2;
		fib1 = next1, fib2 = next2;
		if (fib1 >= MAX_N || fib2 >= MAX_N)break;
	}
	int last = 3;
	for (int i = 4; i<MAX_N; i++)
	{
		if (Zec[i] != 0)last = i;
		else Zec[i] = Zec[i - last];
	}
}

fibo함수에 피보나치 수를 담는 코드가 있는데, 나중에 요긴하게 쓰일 겁니다. 피보나치 수들을 구하는 과정을 조금 복잡하게 적은 것 같은데, 편하신대로 작성하시면 됩니다. 자, 이제 Zec배열은 구했고, ans값만 구하면 되겠죠? 피보나치 수들은 ans값이 -1 임을 우리는 알고 있습니다. 그럼 이제 (2) 번 자료를 봅시다. -1 값이 나올 때마다 개행을 했는데, 각 행의 요소의 개수가 절묘하게도 피 보나 치수입니다. ans값은 다음과 같이 정의됩니다.

{n| n보다 작은 가장 큰 피보나치수를 i라 했을 때, ans [n]=Zec [n% i]}

이 식은 생각보다 직관적입니다. (2) 번 자료에서 같은 열끼리는 같은 값이라는 점을 이용하기 때문이죠. 이제 마지막으로 getAns() 함수를 구현하면 됩니다.

int getAns(int n)
{
	for (int i = 0; i<fibo.size() - 1; i++)
	{
		if (n == fibo[i] || n == fibo[i + 1])return -1;
		if (fibo[i]<n&&n<fibo[i + 1])return Zec[n%fibo[i]];
	}
	return Zec[n%fibo.back()];
}

아까 구한 피보나치 수 들을 여기서 이용합니다. 1백만 이하의 피보나치 수들의 개수는 충분히 작으니 걱정은 없습니다. 이제까지 구한 모든 함수들을 합쳐 솔루션을 구현합시다. 다만 처음 그런디 수를 구할 때 썼던 f함수는 생략을 하겠습니다.

#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX_N = 1000001;
int Zec[MAX_N];
vector<int>fibo;

void getZec()
{
	memset(Zec, 0, sizeof(Zec));
	int fib1 = 1, fib2 = 2;
	while (true)
	{
		fibo.push_back(fib1);
		Zec[fib1] = fib1, Zec[fib2] = fib2;
		int next1 = fib2, next2 = fib1 + fib2;
		fib1 = next1, fib2 = next2;
		if (fib1 >= MAX_N || fib2 >= MAX_N)break;
	}
	int last = 3;
	for (int i = 4; i<MAX_N; i++)
	{
		if (Zec[i] != 0)last = i;
		else Zec[i] = Zec[i - last];
	}
}

int getAns(int n)
{
	for (int i = 0; i<fibo.size() - 1; i++)
	{
		if (n == fibo[i] || n == fibo[i + 1])return -1;
		if (fibo[i]<n&&n<fibo[i + 1])return Zec[n%fibo[i]];
	}
	return Zec[n%fibo.back()];
}

int main()
{
	getZec();
	int N;
	cin >> N;
	cout << getAns(N);
}

길고 길었던 여정이 끝났습니다. 대부분의 그런디 이론 문제가 그렇듯, 그런디 수를 구하는 것은 쉽습니다. (물론 상대적으로) 규칙을 찾고 구현하는 점이 힘들어서 그렇지.. 그런 점에서 그런디이론 문제들은 다른 일반적 문제들보다 차별점도 있고 재밌습니다. 그런디 수의 규칙을 찾아 데이터베이스를 구현해서 하는 문제들도 참 독특하고요. 

앞서 말한 Zec배열의 이름이 왜 Zec인지 간단하게 설명하겠습니다. 사실, 우리가 구한 Zec배열은 실제로 따로 이름이 존재하는 배열입니다.  Zeckendorf representation, 제켄도르프 표현이라고 하는데 모든 양의 정수는 비 연속 피보나치수의 합으로 고유하게 표현이 가능하다고 하네요. 예를들어 64는 1+8+55로 표현이 됩니다. 포인트는 비 연속이기 때문에 64=55+5+3+1 같은 꼴은 제켄도르프 표현이 아닙니다. 또한 특이한 점으로는 이러한 표현은 각 단계마다 가능한 가장 큰 피보나치 수를 선택하여 탐욕적으로 접근이 가능합니다. 그런데 이게 {1,2,3,1,5,1,2,8,1,2,3,1,13,1,2,3... } 배열이랑 무슨 관계가 있냐고요? 신기하게도 이 배열은 다음과 동치입니다.

{n| n을 제켄도르프 표현으로 나타냈을 때, 가장 작은 수}

예를 들어 n=11일 때, 제켄도르프 표현으로 나타내면, 11=8+3, 가장작은수=3이 됩니다. 다른수도 여러분이 직접 계산해보세요, 신기하지않나요? 물론 이 문제는 제켄이고 도르프고 뭐고 그냥 구현만 하면 되고 몰라도 문제 푸는대에 아무런 지장이 없습니다. 

추가로, 제가 제켄도르프 표현이라는 유식하게 보이는 말까지 설명을 한 건 이유가 있습니다. 제켄도르프 표현을 알아야 풀 수 있는 문제가 있기 때문이죠. 이 문제의 n제한은 1백만이었습니다. 배열을 최대 크기만큼 선언해도 되었죠. 하지만, n제한이 10^15라면 어떨까요? 여기 그 문제가 있습니다.

https://www.acmicpc.net/problem/2862

2862번: 수학 게임

이 문제는 더 포스팅하지 않아도 이 과정을 쭉 달려오셨다면 충분히 풀 수 있으실 거라 생각합니다. 더 적지 않는 이유는 절대 귀찮아서가 아닙니다.

힌트: upper_bound(fibo.begin(), fibo.end(), n)-fibo.begin()-1