[Python] 백준/BOJ 17291번: 새끼치기 (Silver 2)

💻 Problem

문제 보러 가기

 

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

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

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

 

💡 Approach

먼가.. 문제를 읽어 보니 DP겠다 싶어서.. 1부터 대입을 해봤다.

ㅋㅋㅋㅋㅋㅋㅋㅋㅋ 정말.. 직접 세봤다.. 다소.. 옹졸하지만......... (원랜 글씨체 안저래여 노트 들고 막 쓴 거임 ㅠㅠ!!)

해보니까 짝수일 때는 이전값 3개를, 홀수일 때는 이전값 4개를 더하면 답이 나오는 것이다..!!

DP 점화식 찾기 어려워서 싫어하는데 이건 다행히 쉽게 찾아졌다.

 

✏️ Solution

import sys
input = sys.stdin.readline

N = int(input())
dp = [0] * (max(N, 3) + 1)

dp[1], dp[2], dp[3] = 1, 2, 4

for i in range(4, N + 1):
    dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

    if i % 2 != 0:
        dp[i] += dp[i - 4]

print(dp[N])

dp[i]에 이전 값 3개를 더한 값을 초기화하고 만약 홀수 연도면 dp[i - 4]까지 더하도록 했다.

 

이번에 알게 된 팁(아마도 예전에 배웠는데 까먹은 걸테지만..)은 비트의 맨 끝(LSB, 최하위 비트)으로 홀수/짝수를 결정한다는 것이다.

항상 짝수는 마지막 비트가 0, 홀수는 마지막 비트가 1이기 때문에 i & 1로 홀수/짝수를 판별할 수 있다.

즉, 반복문 안의 코드를 dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] + ((i & 1) * dp[i - 4]) 한 줄로 바꿔도 가능하다.

 

다른 사람 코드를 보니 짝수일 때는 dp[i - 1] * 2 - dp[i - 4] - dp[i - 5], 홀수일 때는 dp[i - 1] * 2인 점화식도 있었다.