17291.md

백준 17291번 새끼치기

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

---

코드 설명

• 짝수 년일때만 홀수 년에 태어나든 짝수 년에 태어나든 3,4분열을 모두 한 벌레가 사망한다.
• dp[i]에 i년 말까지 생존한 벌레 수를, new[i]에 i년에 태어난 벌레 수를 저장해, dp를 구할때 new를 이용한다.

소스코드

• 메모리 : 30860 KB
• 시간 : 68 ms

n = int(input())
dp = [0 for i in range(21)]
new = [0 for i in range(21)]
dp[0], dp[1], dp[2], dp[3] = 0,1,2,4
new[0], new[1], new[2], new[3] = 0,1,1,2

for i in range(4,21):
    new[i] = dp[i-1]
    if i%2 == 0:
        dp[i] = dp[i-1]*2 - (new[i-3]+new[i-4])
    else:
        dp[i] = dp[i-1]*2

print(dp[n])

오답 노트

• 범위를 n+1까지 할 경우 인덱스 범위가 - 가 될 수 있는데 그래서 틀렸다.
• 따라서 범위를 무조건 21까지로 만든 뒤 계산해 줘야 인덱스 범위가 - 가 되지 않는다.

오답 코드

n = int(input())
dp = [0 for i in range(n+1)]
dp[0], dp[1] = 1,1

for i in range(2,n+1):
    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])