[BOJ 6504 // C++] 킬로미터를 마일로

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

 

이번에 볼 문제는 백준 6504번 문제인 킬로미터를 마일로이다.
문제는 아래 링크를 확인하자.

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

6504번: 킬로미터를 마일로

문제에서 말하는 각 수의 피보나치 진법 표현은 제켄도르프 분해(Zeckendorf representation)를 의미한다. 각 수의 제켄도르프 분해는 유일하다는 것이 잘 알려져있다.

 

각 수의 제켄도르프 분해를 구성하는 피보나치 수들을 (마지막 1을 제외하고) 각각 이전 피보나치 수로 대체해 더한 값을 출력해주자.

 

25000 미만의 피보나치 수가 무엇인지는 각 테스트케이스와 상관없이 정해져 있으므로 미리 전처리해두고 사용하자.

 

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

#include <iostream>
using namespace std;

int fib[21];

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

	fib[0] = 1, fib[1] = 2;

	for (int i = 2; i < 21; i++) {
		fib[i] = fib[i - 1] + fib[i - 2];
	}

	int T; cin >> T;
	while (T--) {
		int ans = 0;
		int x; cin >> x;
		for (int i = 20; i > 0; i--) {
			if (x >= fib[i]) x -= fib[i], ans += fib[i - 1];
		}

		cout << ans << '\n';
	}
}