# [Silver V] 킬로미터를 마일로 [문제 링크](https://www.acmicpc.net/problem/6504) ## 문제 설명 <p>상근이는 하프 마라톤(21km 정도) 대회를 준비하러 동해안으로 떠났다. 상근이의 첫 번째 훈련은 21마일을 뛰는 것이었다.</p> <p>21마일을 뛰어보니 21킬로미터를 뛴 것보다 더 지치는 것 같았다. 상근이의 친구 정인이는 마라톤은 21마일이 아니고 21킬로미터라고 알려주었다. 또, 21킬로미터는 13마일 같다는 사실도 알려주었다. 21, 13? 상근이는 깊은 깨달음을 얻었다. 두 숫자 모두 피보나치 숫자이다!</p> <p>피보나치 숫자는 다음과 같이 정의한다.</p> <ul> <li>F₁ = 1</li> <li>F₂ = 2</li> <li>F_n+1 = F_n + F_n-1 (n > 1)</li> </ul> <p>마침 상근이는 훈련을 떠나기 전, 대학에서 피보나치 진법을 배웠다. 모든 양의 정수 X는 서로 다른 피보나치 수의 합으로 나타낼 수 있다. 즉, b_k = 1과 b_i (1 ≤ i < k) = 0 또는 1이면서 x = ∑i=_1..k b_i × F_i을 만족하는 정수 k와 b₁, b₂, ..., b_k가 항상 존재한다. 이러한 표현을 b(x) = (b_k, b_k-1, ..., b₁)와 같이 간편하게 쓰기로 한다. 또, 여러 가지 표현이 생기는 것을 막기 위해 b_i × b_i-1 = 0이어야 한다. (i > 1)</p> <p>예를 들어, 21은 (1, 0, 0, 0, 0, 0, 0)로, 13은 (1, 0, 0, 0, 0, 0)으로 나타낼 수 있다. 상근이는 이런 피보나치 진법을 이용해서 x킬로미터를 y마일로 바꾸는 방법을 만들었다.</p> <p>먼저, x를 피보나치 진법 b(x)로 나타낸다. 그 다음, b(x)를 오른쪽으로 한 비트씩 시프트 시킨다. (맨 마지막 비트는 버린다) 이것을 b(y)라고 한다. 이제 b(y)를 이용해서 y를 계산하면 된다.</p> <p>예를 들어, 42는 피보나치 진법으로 (1, 0, 0, 1, 0, 0, 0, 0)이다. 이걸 오른쪽으로 한 비트씩 시프트 시키면 (1, 0, 0, 1, 0, 0, 0)이 되고, 0×1 + 0×2 + 0×3 + 1×5 + 0×8 + 0×13 + 1×21 = 26이 된다.</p> <p>킬로미터 값이 주어졌을 때, 상근이의 알고리즘을 이용해서 마일로 바꾸는 프로그램을 작성하시오.</p> ## 입력 <p>첫째 줄에 마일로 바꾸려고 하는 킬로미터 값의 수 t가 주어진다. (0 < t < 25000) 다음 t개 줄에는 마일로 바꿀 킬로미터 값 x가 주어진다. (2 < x < 25000)</p> ## 출력 <p>각각의 킬로미터 거리 x에 대해서, 상근이의 알고리즘을 이용해 마일로 바꾼 값 y를 출력한다.</p> ## 풀이 미리 25000까지의 피보나치 수를 구해놓고, x를 피보나치 진법으로 변환해주었습니다. ``` c++ #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); vector<int> fibo = {1, 2}; while(fibo.back()<=25000) fibo.push_back(fibo[fibo.size()-2]+fibo.back()); int t; cin >> t; while(t--) { int x; cin >> x; int ret=0; for(int i=fibo.size()-1;i>=1;i--) { if(x>=fibo[i]) { x -= fibo[i]; ret += fibo[i-1]; } } cout << ret << '\n'; } } ```