문제
실험실에서 새로운 종의 벌레 한 마리가 탄생하였다. 벌레는 스스로 분열하며, 분열하면 자기 자신과 같은 벌레를 한 마리 만들어 내게 된다. 벌레가 분열하는 규칙은 다음과 같다.
벌레는 기준년도 1년 2월에 1마리가 탄생한다. 벌레는 매년 1월이 되면 분열한다. 분열시 본래의 개체는 그대로, 새로운 개체가 하나 탄생하는 것으로 본다. 홀수년도에 탄생한 개체는 3번 분열시, 짝수년도에 탄생한 개체는 4번 분열시 사망한다. 예를 들어, 기준년도 1년 2월에 존재하던 벌레는, 2년 1월, 3년 1월, 4년 1월에 분열하고 사망하여 4년 말에는 존재하지 않게 된다.
이 때, N년 말에 존재하는 벌레의 수를 구하여라.
접근 방식
년도수가 주어지면 그 년도에 존재하는 벌레의 수를 구하는 문제입니다. 여기서 처음에는 벌레 정보를 저장하고 살아있나 죽었나를 확인해서 살아있는 경우에만 증식하고 배열에 추가했습니다. 즉 완전 탐색으로 8ms가 걸렸습니다. 아마 N의 최대가 20이라서 가능했던 것 같습니다.
그런데 문제를 풀고 다른 사람의 풀이를 보니 DP로 더 빠르게 풀수가 있었습니다.
풀이
- 구현
살아있는지 죽었는지 확인하고 살아있다면 증식을 합니다. 만약 홀수년도 벌레는 3번, 짝수년도 벌레는 4번 분열한 경우, 죽었다고 수정합니다.
- DP
벌레가 분열하고 죽는 경우는 홀수년도 벌레는 3번, 짝수년도 벌레는 4번 분열시 죽습니다.
즉, 홀수년도 벌레, 짝수년도 벌레는 짝수년도에만 죽고 홀수년도는 그냥 2배 증가하기만 하면 됩니다.
코드
// DP로 구현
int N;
int dp[21] = {0, 1, 2, 4, 7, };
int sol() {
for (int y = 5; y <= N; ++y) {
dp[y] = dp[y - 1] * 2;
if (y % 2 == 0)
dp[y] = dp[y - 1] * 2 - (dp[y - 4] + dp[y - 5]);
else
dp[y] = dp[y - 1] * 2;
}
return dp[N];
}
int main() {
cin >> N;
cout << sol();
}구현 vs DP
8ms 대 0ms입니다. N이 최대 20이라서 이정도이지만 더 커지면 사용하기 어려울 것 같습니다.