취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2862번 문제인 수학 게임이다.
문제는 아래 링크를 확인하자.

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

이 문제에서 서술하고 있는 게임은 보통 피보나치 님(Fibonacci nim)이라고 불리는 게임이다.

피보나치 님 게임의 필승전략은 주어진 동전의 개수 N을 제켄도르프 분해(Zeckendorf representation)하였을 때 나오는 피보나치 수 가운데 가장 작은 개수만큼의 동전을 가져가는 것이다. 제켄도르프 분해란 자연수를 연속하지 않은 피보나치 수의 합으로 나타내는 것을 의미하는데, 이러한 분해는 모든 자연수 N에 대하여 각각 유일하게 존재한다는 것이 제켄도르프 정리에 의해 보장된다. 이를 구현하면 주어진 문제를 해결할 수 있다.

피보나치 님 게임과 제켄도르프 분해에 대한 자세한 내용은 아래의 링크를 참고하자.

https://en.wikipedia.org/wiki/Fibonacci_nim

https://en.wikipedia.org/wiki/Zeckendorf%27s_theorem

아래는 제출한 소스코드이다.

#include <iostream>
typedef long long ll;
using namespace std;

ll fib[77];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	fib[0] = 1, fib[1] = 2;
	for (int i = 2; i < 77; i++) {
		fib[i] = fib[i - 1] + fib[i - 2];
	}
	
	ll N; cin >> N;
	for (int i = 76; i >= 0; i--) {
		if (N == fib[i]) break;
		if (N > fib[i]) N -= fib[i];
	}
	cout << N;
}