[13270]피보나치킨(코드+풀이)

문제에 앞서 피보나치수열이란?

 

0 1 1 2 3 5 8 13 21 ...... 으로 진행되는 수열인데 

 

F[0]= 0, F[1] = 1 일 때 임의의 위치의 값을 F[n] 이라고 하면 이 수열의 일반항은

F[n] = F[n-1] + F[n-2]

이다. 

 

문제에서는 피보나치킨을 N 명의 사람이 먹을 수 있는  치킨의 수라고 정의한다.

 

이때 N = F[n] 일 경우 피보나치킨의 수는 F[n-1] 이다.

 

그런데 N = F[n]을 만족하는 N 이 아니라면 어떨까? 예를들면 7과 같은 수이다 7 = F[x] 를 만족하는 x의 값이 존재하는가?

 

그렇지 않다.

 

그럼 N = 7일경우 즉 7명이 먹을 피보나 치킨의 수는 몇마리일까?

 

이럴 경우 제켄도로프 정리를 사용하여 피보나 치킨의 수를 구할 수 있는데

 

제켄도로프 정리의 정의는 다음과 같다.

 

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

 

즉 N = F[a] + F[b] 의 꼴로 나타낼 수 있다.

 

이때 F[a] 의 피보나치킨수 F[a-1] 과 F[b]의 피보나치킨 수 F[b-1]  F[a-1] + F[b-1] 이 피보나치 수가 아닌 자연수 N의 피보나치킨수 이다.

 

우리는 이때까지 배운 내용을 개념으로 피보나치킨수를 구하는 알고리즘을 만들어 보려고 한다.

 

1. 어떤수 N이 피보나치수 이면 F[x] = N을 만족할 때 N명의 피보나치킨수는 F[x-1] 이다.

2. 어떤수 N이 피보나치수가 아닐 경우 F[a1] + F[a2] + ... + F[an] =N을

만족하는 것을 찾고 F[a0] + F[a1] + ... + F[an-1] 이 피보나치킨수이다.

 

우선 피보나치 수열을 두가지 방법으로 생각 할 수있는데,

 

첫번째는 

F[n] 까지의 수열을 미리 저장한 후 그때그때 뽑아 쓰는 방법이다. 

fibo[0] = 0;
fibo[1] = 1;
fibo[2] = 1;
for (int i = 3; i < 60; i++) {
    fibo[i] = fibo[i - 1] + fibo[i - 2];
}

- 하지만 피보나치수열의 경우 n이 한없이 켜질경우 증가도가 상상을 초월하기에 메모리의 소비가 크다.

 

 

두번째는

필요할 때마다 F[n] 의 값을 요청하는 Fibo함수를 만드는 방법이다

public static int Fib(int n){
      if(1>=n){
          return n;
      }
      else{
          return Fib(n-2)+Fib(n-1);
      }
  }

- 재귀함수를 통한 방법이라 시간이 꽤나 걸린다. 해당함수의 시간복잡도는 O(2^n) 이다.

 

 

위 문제에서는 사람의 수를 3,000,000,000 으로 정의하였다.

 

N이 3,000,000,000 일 경우 사실 F[x] ~= 3000,000,000 인 x는 그리 크지 않다 적어도 50~60정도일것이라 생각했다.

 

그래서 1번방법으로 fibo 배열에 미리 피보나치수를 다 넣었다.

 

이제 F[x] = N 을 만족하지 못하는 N의 피보나 치킨수를 어떻게 구할 수 있을까?.

 

N = F[a] + F[b] 라고 가정하자, 아닐 수 도 있다.

(N은 두개이상의 서로 다른 피보나치수의 덧셈으로 나타낼 수 있기때문 반드시 두개는 아님)

 

F[a]+ F[b] 일때 F[a] > F[b] 일것이다. F[a]를 어떻게 찾을까? F[n] 에서 n을 증가시켜가며 그 수가 N보다 커질때,

그때 의 F[n]을 찾고 N- F[n-1] 을 하자 N = F[a] + F[b] 일 경우 F[a] 를 뺏다고하자, 남은 N-F[a] = F[b] 일것이고, 

N-F[a] 를 N' 이라고 할때 N' = F[b] 그리고 N' 에 대해 위의 과정을 다시 반복하는것이다.

 

반복은 while문으로, fibo수열에 접근하는것은 미리저장된 배열을 가져오는것으로 했다. 

for문을통해 i를 증가시키고 F[i ] > N이면  N- F[i-1] 하였다.

치킨마릿수는 F[i-1] 의 피보나치킨수 F[i-2]를 더해주었다 (total 변수)

 

N = 2, N=1, N=0 의 경우

 

F[0], F[1], F[2] 의 값이 단순 증가하지 않으나 (0, 1, 1) For문의 i 값은 단순증가하는데 i값과 혼돈이 생겨 무한루프에 빠지는걸 막기위해

N=2, N=1 일경우 따로 처리하였다.

 

아래는 코드이다.

 

import java.util.Scanner;


public class Sep_12 {

    public static void main(String args[]) {
        long[] fibo = new long[61];
        fibo[0] = 0;
        fibo[1] = 1;
        for (int i = 3; i < 60; i++) {
            fibo[i] = fibo[i - 1] + fibo[i - 2];
        }
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long total = 0;
        while (n > 1) {
            for (int i = 0; i < n+2; i++) {
                if (n == 2) {
                    n--;
                    break;
                }
                if (fibo[i] >= n) {
                    n -= fibo[i - 1];
                    total += (fibo[i - 2]);
                    break;
                }
            }
            if (n == 1) {
                total++;
            }
        }
        System.out.println(total);
    }
}
  /*  public static int Fib(int n){
        if(n==1||n==2){
            return 1;
        }
        if(1>=n){
            return n;
        }
        else{
            return Fib(n-2)+Fib(n-1);
        }
    }
}*/