[백준 / BOJ] C++ 17291 새끼치기

17291번: 새끼치기

 

문제

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

17291번: 새끼치기

 

 

풀이

1년에는 1마리, 2년에는 2마리, 3년에는 4마리, 4년에는 8마리가 되었다가 1년에 탄생한 1마리가 죽어 7마리가 된다. 계속해보면 5년에는 14마리가 되고, 6년에는 28마리가 되었다가 2년에 탄생한 1마리와 3년에 탄생한 2마리가 죽어 25마리가 된다. 여기서 홀수년에 탄생한 개체는 3번 분열 후, 짝수년에 탄생한 개체는 4번 분열 후 사망하기 때문에 반드시 짝수 연도에만 벌레가 사망한다.

 

위 흐름을 따르면 (i년의 마리수)는 (i-1년의 마리수) × 2이고 5년 이후 짝수년도에 대해서는 3년 전, 4년 전에 태어난 마리 수를 빼주면 된다. 여기서 3년 전, 4년 전에 태어난 마리 수는 각각 4년 전, 5년 전의 마리수다. 따라서 4년까지는 문제에서도 주어져있기 때문에 미리 값을 할당해 놓고, 5년부터는 바로 앞에서 설명한 것과 같이 하면 된다. (단, 0년에는 0마리가 살았다고 본다.)

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, a[21] = {0, 1, 2, 4, 7};
  cin >> n;
  for (int i = 5; i <= n; i++) {
    a[i] = a[i - 1] * 2; // 분열
    if (!(i & 1)) // 짝수년도일 때
      a[i] -= a[i - 4] + a[i - 5]; // 4년전, 5년전 마리수 빼기
  }
  cout << a[n];
  return 0;
}