[Codility] 13. Fibonacci (FibFrog)

13. Fibonacci

피보나치 기본코드(재귀)

def fibonacci(n):
    if n<=1:
        return n

    return fibonacci(n-1)+fibonacci(n-2)

피보나치 다이내믹코드(더빠름)

def fibonacciDynamic(n):
    fib=[0]*(n+2)
    fib[1]=1
    for i in range(2,n+1):
        fib[i]=fib[i-1]+fib[i-2]

    return fib[n]

13.1 fibfrog

A small frog wants to get to the other side of a river. The frog is initially located at one bank of the river (position −1) and wants to get to the other bank (position N). The frog can jump over any distance F(K), where F(K) is the K-th Fibonacci number. Luckily, there are many leaves on the river, and the frog can jump between the leaves, but only in the direction of the bank at position N.

The leaves on the river are represented in an array A consisting of N integers. Consecutive elements of array A represent consecutive positions from 0 to N − 1 on the river. Array A contains only 0s and/or 1s:

0 represents a position without a leaf; 1 represents a position containing a leaf. The goal is to count the minimum number of jumps in which the frog can get to the other side of the river (from position −1 to position N). The frog can jump between positions −1 and N (the banks of the river) and every position containing a leaf.

Write a function that, given an array A consisting of N integers, returns the minimum number of jumps by which the frog can get to the other side of the river. If the frog cannot reach the other side of the river, the function should return −1.

작은 개구리는 강의 반대편으로 가고 싶어합니다. 그 개구리는 처음에 강의 한쪽 둑(위치 -1)에 위치하고 다른 둑(위치 N)으로 가고 싶어합니다. 그 개구리는 어떤 거리 F(K)도 뛰어넘을 수 있고, 여기서 F(K)는 K번째 피보나치 수이다.

강 위의 잎들은 N개의 정수로 이루어진 배열 A로 표현됩니다. 배열 A의 연속적인 요소들은 강 위의 0부터 N - 1까지의 연속적인 위치들을 나타냅니다. 배열 A는 오직 0과/또는 1만을 포함합니다:

0은 잎이 없는 위치를 나타냅니다;

1은 잎을 포함하는 위치를 나타냅니다.

목표는 개구리가 강 반대편으로 갈 수 있는 최소 점프 횟수를 세는 것입니다 (-1 위치에서 N 위치로). 개구리는 -1 위치와 N 위치(강둑) 사이와 나뭇잎을 포함하는 모든 위치에서 점프할 수 있습니다.

N개의 정수로 구성된 배열 A가 주어졌을 때, 개구리가 강 반대편으로 갈 수 있는 최소 점프 횟수를 반환하는 함수를 작성하십시오. 만일 개구리가 강 반대편에 도달할 수 없다면, 함수는 -1을 반환해야 합니다.

 

def solution(A):
   A = [1] + A + [1] #시작과 끝지점에 1삽입
   matches = [0]*len(A)
   fib = fibonacciDynamic(len(A))
   for e in range(1, len(A) ):
      if A[e] == 0:
         continue
      min_cnt = len(A)
      for j in fib[2:]: #피보나치배열돌기
            # 현재위치랑 피보나치수가 일치하거나, 현재위치가 피보나치수가 크고 점프 전 위치에 온적 있을때(?)
         if e - j == 0 or (e - j >= 0 and matches[e - j] != 0):
            min_cnt = min(min_cnt, matches[e - j] + 1)
      if min_cnt != len(A):
         matches[e] = min_cnt #match[현재위치]에 최소 카운트 삽입
   if matches[-1] != 0:
      return matches[-1]
   else:
      return -1

def fibonacciDynamic(n):
   fib = [0] * (n+2)
   fib[1] = 1
   for i in range(2, n + 2):
      fib[i] = fib[i - 1] + fib[i - 2]
      if fib[i] > n:
         return fib[:i+1]
   return fib