[백준/BOJ][C++] 6504번 : 킬로미터를 마일로(제켄도르프 정리)

6504번: 킬로미터를 마일로

접근 방법

<양의 정수 x를 피보나치 수의 합으로 나타내는 법>

제켄도르프 정리를 안다면 x를 피보나치 수의 합으로 쉽게 나타낼 수 있다.

• 제켄도르프 정리 : '모든 자연수는 연속하지 않는 피보나치 수의 합으로 표현할 수 있고, 그 합의 표현은 유일하다.'

이 정리를 따르면, 'n번째 피보나치 수 <= x < n+1번째 피보나치 수'를 만족하는 n번째 피보나치 수를 x가 0이 될 때까지 계속 빼다 보면 x를 피보나치 수의 합으로 나타낼 수 있다.

 

<x의 범위>

문제를 보면 x의 범위가 '2 < x < 25000'임을 알 수 있다. 문제에 나와있는 피보나치 숫자를 배열해 본다면 다음과 같다.

• 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657

여기서 x의 최댓값인 24999를 만들려면 10946까지의 피보나치 수만 써도 가능하기 때문에, 미리 피보나치 숫자에 대한 배열을 만들어 놓았다.

 

<킬로미터를 마일로 바꾸는 법>

문제에서는 피보나치 진법으로 변환한 후, 한 비트씩 시프트 해서 킬로미터를 마일로 바꾸라고 했는데, 쉽게 풀어서 말하자면 x를 피보나치 수의 합으로 구하는 과정에서, x(킬로미터)에서 n번째 피보나치 수를 뺐다면 ans(마일)에 n-1번째 피보나치 수를 더해주면 되는 것이다. 

주의할 점

• ans를 구하는 for문에서 배열 범위를 벗어나지 않게 신경 써야 한다.
• ios_base::sycn_with_stdio(false), cin.tie(0) 등을 써주지 않으면 시간초과가 난다.

코드

#include<iostream>

using namespace std;

int arr[20];
void fib(){          //피보나치 배열을 미리 만들어놓기
	arr[0] = 1;
	arr[1] = 2;
	for(int i = 2; i < 20; i++)
		arr[i] = arr[i-1] + arr[i-2];
}

int main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	fib();
	int t;
	cin >> t;
	for(int i = 0; i < t; i++){
		int ans = 0;
		int x;
		cin >> x;
		for(int j = 19; j > 0; j--){
			if(x >= arr[j]){
				x -= arr[j];
				ans += arr[j-1];
			}
		}
		cout << ans << "\n";
	}
}