[백준알고리즘] 11444번: 피보나치 수 6 -C++

[백준알고리즘] 11444번: 피보나치 수 6 -C++

11444번: 피보나치 수 6 (acmicpc.net)

11444번: 피보나치 수 6

골드 난이도면서 정답 비율이 높길래 되게 쉬운 문제인 줄 알았다. 근데 난생처음 보는 풀이를 보고 따라 풀었다. 이 문제를 푸는 방법은 2가지가 있다고 한다. 행렬 곱을 이용한 방법과 방정식을 이용한 방법이다. 아래는 방정식으로 문제를 풀었다.

문제를 푸는 방식은 백준 블로그의 글을 참고했다.

피보나치 수를 구하는 여러가지 방법 (acmicpc.net)

피보나치 수를 구하는 여러가지 방법

---

문제 풀이

문제를 푸는 방정식은 백준 블로그를 참고했다. 그래서 따로 풀이는 필요 없을 것 같다. 왜 그런 방정식이 나오는지는 왜 행렬곱으로 구할 수 있는 건지.. 이것만 좀 더 찾아봐야겠다.

 

수가 너무 크니까 기본적으로 사용하던 방법들은 적용이 안돼서 결국 찾아볼 수밖에 없었다. 정답 비율이 이 정도로 높을 일인가 싶다. 다들 방정식을 미리 어디서 공부했던 건가?

 

아래는 방정식을 토대로 만든 소스코드다.

#include <cstdio>
#include <map>

unsigned long long inputFibonacciIndex();
unsigned long long getOrCalculateFibonacci(const unsigned long long ullIndex);
unsigned long long evenFibonacci(const unsigned long long ullIndex);
unsigned long long oddFibonacci(const unsigned long long ullIndex);
unsigned long long multiply(const unsigned long long ullVal1, const unsigned long long ullVal2);
unsigned long long add(const unsigned long long ullVal1, const unsigned long long ullVal2);

const unsigned long long DIVISOR = 1000000007;

std::map<unsigned long long, unsigned long long> mapFibonacci;

int main() {
	unsigned long long ullIndex = inputFibonacciIndex();
	unsigned long long ullResult = getOrCalculateFibonacci(ullIndex);
	printf("%llu", ullResult);
	return 0;
}

unsigned long long inputFibonacciIndex() {
	unsigned long long ullIndex = 0;
	scanf("%llu", &ullIndex);
	return ullIndex;
}

unsigned long long getOrCalculateFibonacci(const unsigned long long ullIndex) {
	if ( 0 == ullIndex || 1 == ullIndex ) {
		return ullIndex;
	}

	if ( mapFibonacci.end() != mapFibonacci.find(ullIndex) ) {
		return mapFibonacci[ullIndex];
	}

	unsigned long long ullVal = 0;
	if ( 0 == ullIndex % 2 ) {
		ullVal = evenFibonacci(ullIndex);
	}
	else {
		ullVal = oddFibonacci(ullIndex);
	}

	mapFibonacci[ullIndex] = ullVal;

	return ullVal;
}

unsigned long long evenFibonacci(const unsigned long long ullIndex) {
	const unsigned long long ullHalf = ullIndex / 2;
	return multiply(
		add(
			multiply(2, getOrCalculateFibonacci(ullHalf - 1)), 
			getOrCalculateFibonacci(ullHalf)
		), 
		getOrCalculateFibonacci(ullHalf)
	);
}

unsigned long long oddFibonacci(const unsigned long long ullIndex) {
	const unsigned long long ullHalf = (ullIndex + 1) / 2;
	return add(
		multiply(getOrCalculateFibonacci(ullHalf), getOrCalculateFibonacci(ullHalf)), 
		multiply(getOrCalculateFibonacci(ullHalf - 1), getOrCalculateFibonacci(ullHalf - 1))
	);
}

unsigned long long multiply(const unsigned long long ullVal1, const unsigned long long ullVal2) {
	return (ullVal1 * ullVal2) % DIVISOR;
}

unsigned long long add(const unsigned long long ullVal1, const unsigned long long ullVal2) {
	return (ullVal1 + ullVal2) % DIVISOR;
}