[백준 17291번] 파이썬 - 새끼치기

백준 17291 - 새끼치기

시간 제한 1초, 메모리 제한 256MB

# 조건

• 실험실에서 새로운 종의 벌레 한 마리가 탄생하였다.
• 벌레는 스스로 분열하며, 분열하면 자기 자신과 같은 벌레를 한 마리 만들어 내게 된다.
• 벌레가 분열하는 규칙은 다음과 같다.
  1. 벌레는 기준년도 1년 2월에 1마리가 탄생한다.
  2. 벌레는 매년 1월이 되면 분열한다. 분열시 본래의 개체는 그대로, 새로운 개체가 하나 탄생하는 것으로 본다.
  3. 홀수년도에 탄생한 개체는 3번 분열시, 짝수년도에 탄생한 개체는 4번 분열시 사망한다.
• 예를 들어, 기준년도 1년 2월에 존재하던 벌레는, 2년 1월, 3년 1월, 4년 1월에 분열하고 사망하여 4년 말에는 존재하지 않게 된다.
• 이 때, N년 말에 존재하는 벌레의 수를 구하여라.

입력

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

출력

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

# 접근 방법

• dp를 이용하여 풀어주었다.
• 짝수년에 탄생한 개체는 4번, 홀수년에 탄생한 개체는 3번 분열 후 죽기에 홀수년도에는 직전 년도 * 2의 개체가 생존하고, 짝수 년도에는 직전 년도 * 2에서
  • 4년전 탄생한 개체 수, 3년 전 탄생한 개체 수만큼 빼주어야 한다.
• 즉, 짝수 년도에는 2년 전의 개체 수에서 3년전의 개체 수 차이만큼 빼주면 된다.
  • 3년전의 개체수는 4년전의 개체가 포함되어 있고, 2년 전의 개체수에는 이미 죽은 개체 수가 포함되어 있기 때문!

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline

N = int(input())
lives = [0] * (21)
lives[0] = 1
lives[1] = 1
lives[2] = 2
lives[3] = 4

for i in range(4, 21):
    if not i % 2:
        lives[i] = lives[i-1] * 2 - (lives[i-2] - lives[i-3])
    else:
        lives[i] = lives[i-1] * 2
print(lives[N])