[BOJ/백준] 17291번 새끼치기 (Python 파이썬)

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

17291번: 새끼치기

 

문제

실험실에서 새로운 종의 벌레 한 마리가 탄생하였다. 벌레는 스스로 분열하며, 분열하면 자기 자신과 같은 벌레를 한 마리 만들어 내게 된다. 벌레가 분열하는 규칙은 다음과 같다.

1. 벌레는 기준년도 1년 2월에 1마리가 탄생한다.
2. 벌레는 매년 1월이 되면 분열한다. 분열시 본래의 개체는 그대로, 새로운 개체가 하나 탄생하는 것으로 본다.
3. 홀수년도에 탄생한 개체는 3번 분열시, 짝수년도에 탄생한 개체는 4번 분열시 사망한다.

예를 들어, 기준년도 1년 2월에 존재하던 벌레는, 2년 1월, 3년 1월, 4년 1월에 분열하고 사망하여 4년 말에는 존재하지 않게 된다. 이 때, N년 말에 존재하는 벌레의 수를 구하여라.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 20)이 주어진다.

출력

첫째 줄에 N년 말에 존재하는 벌레의 수를 출력한다.

예제 입력 1 

4

예제 출력 1 

7

• 1년 2월, 1마리 탄생
• 2년 1월, 분열 > 2마리 생존
• 3년 1월, 분열 > 4마리 생존
• 4년 1월, 분열 > 7마리 생존 ( 1년 2월에 태어난 1마리 사망 )
• 4년 말, 7마리 생존

 

---

풀이

문제를 정리하면, 홀수년에 태어난 벌레는 3번 분열 후 죽고, 짝수년에 태어난 벌레는 4번 분열 후에 죽습니다.

점화식을 찾기 위해 정리하면 아래와 같은 결론이 나옵니다.

따라서, (1) 연초에 분열을 통해 개체수를 2배로 증가시킨 후 (2) 연말에 수명이 다된 개체수는 사망시키는 작업을 반복합니다.

이때, i년에서의 사망수는 위에서 정리했듯이 i-4년생의 수 + i-5년생의 수 입니다.

따라서 i년에 태어난 벌레의 수를 담은 dp 리스트를 선언하여 아래와 같이 구현할 수 있습니다.

Code

from sys import stdin
N = int(stdin.readline())

# i년에 태어난 벌레의 수
dp = [0] * (21)
dp[0], dp[1] = 1, 1  # dp[0]-> dp[4] 계산시 필요

for i in range(2, N+1):
    # 분열
    dp[i] = dp[i-1]*2
    # 사망
    dp[i] -= dp[i-4] + dp[i-5] if not i % 2 else 0
print(dp[N])