[python/파이썬] 백준 17291 새끼치기

[문제 출처]

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

17291번: 새끼치기

 

[문제 풀이 ] 

 

num list에 연도 말에 존재하는 개체수를 저장한다. 

그리고 death list에 해당 연도에 죽는 개체수를 저장한다. 

 

태어날 때 그 해가 홀수년인지 짝수년인지 확인하고 죽는 년도를 계산하여 death에 저장한다.

 

i번째 연도에는 i-1번째 연도의 개체수만큼 태어나므로 

홀수년이면 i+3년에 i년에 태어난만큼 더 죽고, 짝수년이면 i+4년에 i년에 태어난 만큼 더 죽는다.

 

i년의 개체수는 분열하므로 전년도 개체수의 두배를 하고 죽는 개체수만큼 빼서 저장하였다.

 

import sys
input = sys.stdin.readline

n = int(input())

death =[0 for _ in range(21)]
num = [0 for _ in range(21)]
num[1] = 1
death[4] = 1

for i in range(2,21):
    birth = num[i-1]
    num[i] = num[i-1] * 2 - death[i]   
    
    if i%2 == 0:
        if i+4 <= 20:
            death[i+4] += birth
    else:
        if i+3 <= 20:
            death[i+3] += birth
print(num[n])