[BAEKJOON] 백준 6504: 킬로미터를 마일로 (C#)

문제 링크

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

 

 

문제

상근이는 하프 마라톤(21km 정도) 대회를 준비하러 동해안으로 떠났다. 상근이의 첫 번째 훈련은 21마일을 뛰는 것이었다.

21마일을 뛰어보니 21킬로미터를 뛴 것보다 더 지치는 것 같았다. 상근이의 친구 정인이는 마라톤은 21마일이 아니고 21킬로미터라고 알려주었다. 또, 21킬로미터는 13마일 같다는 사실도 알려주었다. 21, 13? 상근이는 깊은 깨달음을 얻었다. 두 숫자 모두 피보나치 숫자이다!

피보나치 숫자는 다음과 같이 정의한다.

• F1 = 1
• F2 = 2
• Fn+1 = Fn + Fn-1 (n > 1)

마침 상근이는 훈련을 떠나기 전, 대학에서 피보나치 진법을 배웠다. 모든 양의 정수 X는 서로 다른 피보나치 수의 합으로 나타낼 수 있다. 즉, bk = 1과 bi (1 ≤ i < k) = 0 또는 1이면서 x = ∑i=1..k bi × Fi을 만족하는 정수 k와 b1, b2, ..., bk가 항상 존재한다. 이러한 표현을 b(x) = (bk, bk-1, ..., b1)와 같이 간편하게 쓰기로 한다. 또, 여러 가지 표현이 생기는 것을 막기 위해 bi × bi-1 = 0이어야 한다. (i > 1)

예를 들어, 21은 (1, 0, 0, 0, 0, 0, 0)로, 13은 (1, 0, 0, 0, 0, 0)으로 나타낼 수 있다. 상근이는 이런 피보나치 진법을 이용해서 x킬로미터를 y마일로 바꾸는 방법을 만들었다.

먼저, x를 피보나치 진법 b(x)로 나타낸다. 그 다음, b(x)를 오른쪽으로 한 비트씩 시프트 시킨다. (맨 마지막 비트는 버린다) 이것을 b(y)라고 한다. 이제 b(y)를 이용해서 y를 계산하면 된다.

예를 들어, 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이 된다.

킬로미터 값이 주어졌을 때, 상근이의 알고리즘을 이용해서 마일로 바꾸는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 마일로 바꾸려고 하는 킬로미터 값의 수 t가 주어진다. (0 < t < 25000) 다음 t개 줄에는 마일로 바꿀 킬로미터 값 x가 주어진다. (2 < x < 25000)

 

 

출력

각각의 킬로미터 거리 x에 대해서, 상근이의 알고리즘을 이용해 마일로 바꾼 값 y를 출력한다.

 

 

 

통과한 답안

using System.Text;

namespace _6504
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int t = int.Parse(Console.ReadLine());
            StringBuilder sb = new StringBuilder();

            List<int> kilometers = new List<int>();

            for (int i = 0; i < t; i++)
            {
                kilometers.Add(int.Parse(Console.ReadLine()));
            }

            List<int> fibonacci = GenerateFibonacci(25000);

            foreach (var km in kilometers)
            {
                int miles = ConvertMiles(km, fibonacci);
                sb.AppendLine(miles.ToString());
            }

            Console.WriteLine(sb.ToString());
        }

        static List<int> GenerateFibonacci(int max)
        {
            List<int> fibonacci = new List<int> { 1, 2 };
            while (true)
            {
                int nextFibo = fibonacci[fibonacci.Count - 1] + fibonacci[fibonacci.Count - 2];
                if (nextFibo > max) break;
                fibonacci.Add(nextFibo);
            }

            return fibonacci;
        }

        static int ConvertMiles(int km, List<int> fibonacci)
        {
            List<int> fibonacciRep = new List<int>();

            for (int i = fibonacci.Count - 1; i >= 0; i--)
            {
                if (fibonacci[i] <= km)
                {
                    km -= fibonacci[i];
                    fibonacciRep.Add(1);
                }
                else
                {
                    if (fibonacciRep.Count > 0)
                    {
                        fibonacciRep.Add(0);
                    }
                }
            }

            if (fibonacciRep.Count > 0)
            {
                fibonacciRep.RemoveAt(fibonacciRep.Count - 1);
            }

            int miles = 0;
            for (int i = 0; i < fibonacciRep.Count; i++)
            {
                if (fibonacciRep[i] == 1)
                {
                    miles += fibonacci[fibonacciRep.Count - 1 - i];
                }
            }

            return miles;
        }
    }
}

 

주어진 킬로미터를 마일로 변환하는 알고리즘을 만드는 문제인데,

킬로미터를 피보나치 수열의 합으로 찾은 후에

그 배열을 오른쪽 비트 시프트를 이용해서 마일을 구하는 방법을 구현한 문제였다.

 

킬로미터를 가지고 피보나치 수열의 합으로 작성하는 부분이 까다로웠던 문제로

우선 피보나치 수열을 리스트로 최대 수인 25000까지 생성한 뒤에

이 피보나치 수열을 이용해서 주어진 km를 표현하고,

그 수열을 바탕으로 마지막 숫자를 지우는 방식으로 오른쪽 비트 시프트를 구현하였다.

그 후에 이 숫자들을 피보나치 수열과 매칭시켜서 마일을 구하는 방식으로 구현하였다.

 

km와 mile의 관계가 피보나치 수열로 성립시킬 수 있다는 점이 놀랐던 문제로

오른쪽 비트 시프트를 구현하는 방법과 인덱스가 까다로웠던 문제였다.