[Algorithm] 피보나치킨 / Fiona-chicken

알고리즘 수업 첫주차 실습 !

알고리즘과는 별로 안친하고,, 친해지려고 노력하고 싶은,,, 사람으로써,,,, 여기에 푼 해답 코드는 모두,,,, 완벽하고,, 막그런 코드는 아니니,,, 유의하시길,,,, 내멋대로 내맘대로 푸는 코드...!!!

 

Description

여러 명의 사람들을 위한 치킨을 준비하려고 한다.

피보나치 수열(Fibonacci Numbers)과 제켄도르프 정리(Zeckendorf's Theorem)를 이용하여, 인원 수가 주어졌을 때 필요한 치킨의 양을 구하여라.

 

Input 

주어진 사람의 수 (입력되는 값은 문자열 형태의 값임. 형변환 후 사용할 것)

입력 값은 최대 300,000,000 이하의 자연수

 

Output 

필요한 치킨의 마리 수

 

Sample Input

17

 

Sample output

11

---

1️⃣ 피보나치 수열(Fibonacci Numbers)

피보나치 수열은 다음과 같은 점화식으로 표현되는 수열이다.

F_0=0,  F_1=1,  F_n=F_(n-1)+F_(n-2)

 

피보나치 수열의 항들을 나열하면 다음과 같다.

ex)

•F_0=0

•F_1=1

•F_2=1

•F_3=2

•F_4=3

•F_5=5

•F_6=8

•F_7=13

•F_8=21

•F_9=34

•F_10=55

 

문제에서의 피보나치 수열을 살펴보자!

피보나치수열은 F,

치킨을 먹을 사람의 수(Input)을 N이라고 하고,

N에 해당하는 피보나치 인덱스를 α 라고 하자.

F_α=N 일때, 필요한 치킨의 양(output)은 F_(α-1)이 된다!

 

예시

 

2명(=F_3)이 먹어야할 치킨의 수는 1마리(=F_2)

3명(=F_4)이 먹어야할 치킨의 수는 2마리(=F_3)

 

❗️여기서 피보나치 수열에 의해 정의될 수 없는 수, 예를들면 4! 는 최적화된 치킨의 수를 구할 수 없다는 문제점이 있다❗️-> 이 경우, 제켄도르프정리를 이용한다.

 

2️⃣ 제켄도르프 정리 (Zeckendorf's Theorem)

제켄도르프의 정리는,

"어떤 자연수를 서로 다른 피보나치 수의 합으로 표현하되, 연속하거나 중복된 두 항을 더하지 않게 하는 방법은 유일하다." 라는 정리

 

즉, 임의의 자연수 n을 연속하지 않는 피보나치 수로 분해할 수 있다.

•4=3+1=F_4+F_2

•7=5+2=F_5+F_3

•17=13+3+1=F_7+F_4+F_2

•2000=1597+377+21+5=F_17+F_14+F_8+F_5

 

잘못된 예:

•17=8+8+1=F_6+F_6+F_2   ->  중복된 두 항

•17=8+5+3+1=F_6+F_5+F_4+F_2   -> 연속된 두 항

 

다시 문제로 돌아가보자!

제켄도르프 분해를 사용하면 모든 자연수로 된 인원수에 대해서, 최적의 치킨의 양을 도출할 수 있다.

• 4명일 경우, 4 = 3 + 1 = F_4 + F_2

  치킨의 수 -> F_3 + F_1 = 3 마리

 

• 17명일 경우, 17 = 13 + 3 + 1 = F_7 + F_4 + F_2

  치킨의 수 -> F_6 + F_3 + F_1 = 11 마리

 

---

문제 풀이 코드 (C++)

#include <iostream>
using namespace std;

// 피보나치 수열
int fibo(int n){
    int i, f1=1, f2=1, f3;
    
    if(n<2)
        return 1;
    
    for(int i=2;i<=n;i++){
        f3 = f1+f2;
        f1 = f2;
        f2 = f3;
    }

    return f3;
}

// 피보나치킨의 수 구하기 (= 최적의 수)
int fibonacchicken(int n){
    int i, result = 0;
    int s;

    if(n==1)
        return 1;
    
    for (i=0;i<=n;i++){
    	// 피보나치 수열에 있는 수일 경우,
        if(n==fibo(i)){
        	// 피보나치 함수에 (index-1) 한 index 값으로 전달
            result = fibo(i-1);
            break;
        }
        // 피보나치 수열에 없는 수일 경우,
        else if(n<fibo(i)){
            for(int j=i-1;j>0;j--){
                if(n>=0){
                	// index 값을 하나씩 줄여가며 사람 수에서 피보나치수의 값을 뺌
                    n-=fibo(j);
                    // 사람의 수가 0이 될때까지
                    if(n>=0){
                    // 해당 인덱스에서 -1 한 값을 피보나치 함수로 다시돌리고 result 값으로 축적
                    s=j-1;
                    result +=fibo(s);
                    }
                    // 사람의 수가 음수인 값이 된다면
                    else{
                    	// 뺐던 값을 다시 더해줌
                        n+=fibo(j);
                    }
                }
                else if(n<0)
                {
                    break;
                }
            }
        }
    }
    return result;
}


int main(){
    int n; //주어진 사람 수
    cin >> n;

    cout << fibonacchicken(n) <<endl;
}