📝아이디어 스케치

• 피보나치 수열이 자연현상을 잘 설명하듯, N명의 사람이 먹을 치킨의 수를 비례적으로 구해준다고 합니다. 웹에 만들어진 프로그램을 직접 구현해보았습니다.

• memory: Dict{}를 기준 사람의 수n이 주어졌을 때

  • key k(피보나치 수열의 순번)의 value(사람의 수, N_person)가 n일때
  • 먹어야 하는 치킨의 수는 key k-1번째의 value(치킨의 수, N_chicken)이다.

• 만약 사람의 수value n 이 memory에 없다면
  더해서 n이 되는 자연수들의 집합을 찾는 알고리즘(치킨도르프)이 필요하다.

  • 이때 임의의 집합이 아닌, 다음 알고리즘을 이용하여 집합을 선택한다.
    1. 무조건 가장 큰 k-1번째 항을 사용하여 N_person:=0을 목표값 n까지 더해 나감
    2. 남은 항들을 역순으로 순회하면서 제일 큰 값 부터 차례로 더함
    3. N_person == n 일 때 까지 반복

🔧 구현

def FibonaChicken(k):
    if k in memory.keys() :
        memory[k]
    else :
        memory[k] = FibonaChicken(k-2) + FibonaChicken(k-1)
    return (n_person := memory[k])
print(FibonaChicken(6))
print(memory)

8
{1: 1, 2: 1, 3: 2, 4: 3, 5: 5, 6: 8}

def FibonaChicken_General(n):
    k = 1
    while FibonaChicken(k) < n:
        k += 1
        
    for k, n_person in memory.items() :
        if n_person == n :
            if n == 1 :
                N_chicken = memory[1]
            else:
                N_chicken = memory[k-1]
            print(f'피보나치킨 님께서 이르시기를 치킨을 {N_chicken}개 시키도록 하여라!')
            return N_chicken
    print("치킨도르프 님께서 이르시기를", end = ' ')
    N_chicken = ChickenDorf(n)
    print(f'치킨을 {N_chicken}개 시키도록 하여라!')
    
def ChickenDorf(n):
    N_chicken = 0
    N_person = 0
    max_k = len(memory) - 1
#     print(f'max_k는 {max_k}')
    #일단 max_k key : value를 더함
    # max_k - 1 key : value를 더하는데 이때 n보다 작다면 수행
    # max_k - k key : value 까지 가면서 더해서 n을 만듦
    N_person = memory[max_k]
    rest = n - N_person
    N_chicken = memory[max_k-1]
#     print(f'목표 사람 수는 {n}명 이고 현재 {N_person}명 고려 됨 ({rest}명 남음)\
#           이에 따라 현재 치킨 {N_chicken}개 필요함')
    for k, n_person in reversed(memory.items()) :
        if n_person <= rest:
            N_person += n_person
            N_chicken += memory[k-1]
            rest -= n_person
            if rest == 0 : break         
    return N_chicken

memory = {1:1, 2:1}
FibonaChicken_General(3)

피보나치킨 님께서 이르시기를 치킨을 2개 시키도록 하여라!

memory = {1:1, 2:1}
FibonaChicken_General(4)

치킨도르프 님께서 이르시기를 치킨을 3개 시키도록 하여라!

memory = {1:1, 2:1}
FibonaChicken_General(int(input('몇 사람이 먹을 것이냐')))

몇 사람이 먹을 것이냐30
치킨도르프 님께서 이르시기를 치킨을 19개 시키도록 하여라!

😎끝.