17291번: 새끼치기
실험실에서 새로운 종의 벌레 한 마리가 탄생하였다. 벌레는 스스로 분열하며, 분열하면 자기 자신과 같은 벌레를 한 마리 만들어 내게 된다. 벌레가 분열하는 규칙은 다음과 같다. 벌레는 기준
www.acmicpc.net
dp로 풀 수 있고, 단순 구현으로도 풀수 있다. 나는 dp로 풀었다.
홀수년도와 짝수년도에 태어난 세포는 모두 짝수년도에 소멸하고, 소멸하는 수는 그 전년도의 세포의 수이다.
즉, i 년에 태어난 세포의 수 = (i - 1)년에 존재한 세포의 수이다.
점화식은,
k가 짝수일 때,
\(dp[k] = dp[k-1] * 2 - (dp[k-4] + dp[k-5])\)
k가 홀수일 때,
\(dp[k] = dp[k-1] * 2\)
가 된다.
|
1
2
3
4
5
6
7
8
9
|
n=int(input())
dp = [0 for _ in range(21)]
dp[0]=1;dp[1]=1
for i in range(2, 21):
if i%2 == 0:
dp[i] = dp[i-1] * 2 - dp[i-4] - dp[i-5]
else:
dp[i] = dp[i-1] * 2
print(dp[n])
|
cs |
'백준 문제풀이' 카테고리의 다른 글
| 백준 16991 - 외판원 순회 3 [Python] (0) | 2021.04.28 |
|---|---|
| 백준 1306 - 달려라 홍준 [Python] (0) | 2021.04.08 |
| 백준 1321 - 군인 [Python] (0) | 2021.04.08 |
| 백준 16895 - 님 게임 3 [Python] (2) | 2021.04.01 |
| 백준 17371 - 이사 [Python] (0) | 2021.04.01 |