[Python/BOJ] 13270. 피보나치 치킨

https://www.acmicpc.net/problem/13270

13270번: 피보나치 치킨

문제

KAIST 주변에서 먹을 수 있는 배달 음식들은 대부분 치킨이다. 이렇게 치킨집이 포화 상태지만 지훈이는 카이스트 주변에 새로 치킨집을 창업했는데, 생각보다 장사가 잘 되었다!

알고 보니 그가 차린 치킨집의 신기한 방식 때문에 장사가 잘 된다고 한다. 지훈이의 치킨집에 치킨 주문을 하는 것은 간단하다. 어차피 지훈이네 치킨집의 메뉴는 도깨비오븐구이 하나이므로, 치킨 먹을 사람 수만 이야기하면, 그 사람 수에 맞는 치킨을 배달하는 것이다.

치킨의 마리 수를 정하는 방법은 다음과 같다:

1. 2인 1닭, 3인 2닭, 5인 3닭, 8인 5닭, 13인 8닭 … 등 피보나치 수열의 인접한 두 수를 이용해(항상 사람의 수 > 닭의 수가 되어 야 한다) 치킨 세트를 만든다.
2. 이 세트들을 적절히 조합해서 총 합이 정확히 N인분이 되도록 만든다.
3. 2번 과정에서 조합한 세트들을 배달한다.

어느 날, 지훈이의 치킨집 단골인 태영이가 N명이 먹을 것을 주문하면 배달되는 치킨 수의 범위가 궁금해졌다. 똑같이 N인분을 주문한다고 해서 항상 같은 마리수의 닭이 오는 것은 아니기 때문이다. 예를 들어, N=6 일 경우, “2인 1닭” 세트를 3개 배달하면 총 3마리가 오는 반면, “3인 2닭” 세트를 2 개 배달하면 총 4마리까지 올 수도 있다. 태영이는 이미 답을 알고 있으나 계산하기 귀찮은 나머지 여러분들에게 프로그램을 만들라고 시켰다.

치킨은 좋아하는 여러분들도 답이 궁금할 것이라고 생각되므로 이 문제를 풀어보자. N이 주어졌을 때 배달되는 치킨 수의 최솟값과 최댓값을 구하면 된다.

입력

첫째 줄에 사람의 수 N이 주어진다. N은 2016년에 재학 중이었던 카이스트 학생 수보다는 작거나 같은 2 이상의 정수이다.

출력

배달되는 치킨 수의 최솟값과 최댓값을 띄어쓰기로 구분하여 출력한다.

풀이

Code

import sys
input = sys.stdin.readline

def solution(n) :
    # 1. 최댓값, 최솟값 DP 생성
    INF = int(1e9)
    max_dp, min_dp = [-INF for _ in range(n+1)], [INF for _ in range(n+1)]
    max_dp[0], min_dp[0], = 0, 0
    # 2. 피보나치 변수 생성
    now, pre = [2, 1], [1, 1]
    # 3.
    while now[0] <= n :
        p, c = now[0], now[1]
        for i in range(p, n+1) :
            # 3-1. 최댓값 업데이트
            if max_dp[i - p] != -INF or i % p == 0 : max_dp[i] = max(max_dp[i], max_dp[i-p] + c)
            # 3-2. 최솟값 업데이트
            if min_dp[i - p] != INF or i % p == 0 : min_dp[i] = min(min_dp[i], min_dp[i-p] + c)
        # 3-3. 피보나치 변수 업데이트
        now, pre = [a + b for a, b in zip(now[:], pre[:])], now[:]
    # 4. 결과 출력
    print(f'{min_dp[-1]} {max_dp[-1]}')

if __name__ == "__main__" :
    n = int(input())
    solution(n)