BOJ/백준-9507-python

문제

풀이

• 피보나치 + 점화식 문제로 대표적인 다이나믹 프로그래밍 문제이다.

n	값
0	1
1	1
2	2
3	4
4	d[n-1] + d[n-2] + d[n-3] + d[n-4]
5	d[n-1] + d[n-2] + d[n-3] + d[n-4]

• 위 테이블과 문제 조건에서 확인할 수 있듯이 n이 4이상일 때부터 일정 규칙을 따르므로 해당 규칙을 구현하면 된다.
• bottom-up 방식으로 구현했다.

코드

# https://www.acmicpc.net/problem/9507
# boj, 9507: Generations of Tribbles, python3
import sys

input = sys.stdin.readline

def dp(n):
    # 앞서 계산된 결과를 저장하기 위한 dp 테이블 초기화
    d = [0] * 68
    # 문제 조건에서 정의된대로 값 할당
    d[0] = 1
    d[1] = 1
    d[2] = 2
    d[3] = 4

    # dp bottom-up
    for i in range(4, n+1):
        d[i] = d[i-1] + d[i-2] + d[i-3] + d[i-4]

    return d[n]

if __name__ == '__main__':
    t = int(input())
    nums = [int(input()) for _ in range(t)]

    for x in nums:
        print(dp(x))

결과

출처 & 깃허브

BOJ 9507
github