[백준 17291] 새끼치기

문제

www.acmicpc.net/problem/17291

 

알고리즘

DP

 

풀이

기준년도 1년 2월에 개체가 +1 생겼을 때, $N$년도후의 개체수를 묻고 있습니다. 홀수년도에 태어난 개체는 3번 분열 후 죽고, 짝수년도에 태어난 개체는 4번 분열 후 죽습니다.

 

DP는 최적해를 구할 때(최댓값, 최솟값)뿐만 아니라 순차적으로 진행해나가는 문제에서도 사용할 수 있습니다.

 

$cache[i]$=$i$년도에 존재하는 개체수

 

위와 같이 설정하고 풀어나가면 됩니다.

 

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

int N;
int cache[30];

int main() {
    FAST;
    cin >> N;
    cache[0]=cache[1] = 1;
    
    for (int i = 1;i < N;++i) {
        cache[i + 1] = cache[i] * 2;
        //cache[i-3], cache[i-4]는 각각 홀수, 짝수년도에 새로 태어난 개체의 수이다.
        if (i + 1 - 3 >= 1 && (i - 2) % 2 == 1) cache[i + 1] -= cache[i-3];
        if (i + 1 - 4 >= 1 && (i - 3) % 2 == 0) cache[i + 1] -= cache[i-4];
    }
    cout << cache[N];	

    return 0;
}