Tribonacci Sequence

문제 설명

Well met with Fibonacci bigger brother, AKA Tribonacci.

As the name may already reveal, it works basically like a Fibonacci, but summing the last 3 (instead of 2) numbers of the sequence to generate the next. And, worse part of it, regrettably I won't get to hear non-native Italian speakers trying to pronounce it :(

So, if we are to start our Tribonacci sequence with [1, 1, 1] as a starting input (AKA signature), we have this sequence:

[1, 1 ,1, 3, 5, 9, 17, 31, ...]

But what if we started with [0, 0, 1] as a signature? As starting with [0, 1] instead of [1, 1] basically shifts the common Fibonacci sequence by once place, you may be tempted to think that we would get the same sequence shifted by 2 places, but that is not the case and we would get:

[0, 0, 1, 1, 2, 4, 7, 13, 24, ...]

Well, you may have guessed it by now, but to be clear: you need to create a fibonacci function that given a signature array/list, returns the first n elements - signature included of the so seeded sequence.

 

제한 사항

Signature will always contain 3 numbers; n will always be a non-negative number; if n == 0, then return an empty array (except in C return NULL) and be ready for anything else which is not clearly specified ;)

 

 

해결 방법

피보나치 수열은 앞의 두 값의 합을 더한 수열이다.

이 문제는 트라이보나치 수열로 값을 두 개가 아닌 세 개를 더해 배열로 만드는 문제다.

 

1. 제한 조건을 맞추기 위해 n이 0이라면 빈 배열을 반환한다.
2. signature의 요소수의 -3 만큼 반복한다.
   (기본 값으로 3개의 값이 주어지므로 최종 반환시에는 -3만큼 반환)
3. 반복 수를 기준으로 슬라이싱하여 3개의 값이 더해지도록 반복한다. 
4. 더한 값을 다시 배열에 담는다.
5. 최종 배열을 제시된 n의 수만큼 슬라이싱하여 반환한다.
   (기본으로 주어진 3개 요소보다 적은 n이 있을 수 있기 때문)

def tribonacci(signature, n):
    if n == 0 :
        signature = []
    else:
        for i in range(n-3):
            signature.append(sum(signature[i:]))
        signature = signature[:n]
    return signature

 

 

 

아래는 베스트로 뽑힌 코드이다.

def tribonacci(signature, n):
    res = signature[:n]
    for i in range(n - 3): 
        res.append(sum(res[-3:]))
    return res

signature[:n] 으로 하면 if 로 n == 0을 연산할 필요도 없고, 최종 배열 반환의 길이도 굳이 자를 필요가 없게 된다.

 

n이 0이고 0으로 슬라이싱을 하게 되면 빈배열을 반환한다.

n이 3이하면 반복문에서 -3만큼 반복하기 때문에 반복을 하지않고 그대로 반환한다.