[백준 17291번] 새끼치기 (C++)

문제링크 : https://www.acmicpc.net/problem/17291

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = INT_MAX;

int N;
int dp[20];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N;

    dp[0] = dp[1] = 1; //초기값
    for(int i=2; i<=N; i++)
    {
        dp[i] = dp[i-1] * 2; //매번 분열
        if(i%2==0) dp[i] -= (dp[i-4] + dp[i-5]); //짝수 일때만 감소
    }

    cout << dp[N];

    return 0;
}

 

기본적으로 매년 분열하므로, dp식을 매번 직전 값에 2배를 해준다.

이후 감소되는 케이스를 보면, 짝수년도 4번 분열 + 홀수년도 3번 분열이므로 사실상 짝수년도에서만 분열되었던 값들이 사라지게 되는 것을 알 수 있다.

 

이에 4번 분열된 값들의 경우 그 직전인 i-5의 값을, 3번 분열된 값들의 경우 그 직전인 i-4의 값을 감소시켜주면 된다.

4번 분열된 값이라고 i-4의 값을 체크하면, 이는 직전 분열된 값이 껴 있는 상태이므로, 제거 대상인 분열된 값은 그 직전위치의 값이 된다.

1 1
2 1 + 1 (직전 분열 1, 새롭게 분열 1)
3 1 + 1 / 1 + 1 (직전 분열 1 + 1, 새롭게 분열 1 + 1)
4 1 + 1 1 + 1 / 1 + 1 1 + 1 (직전 분열 1 + 1 1 + 1, 새롭게 분열 1 + 1 1 + 1)
.
.
6 
3 + 3, 2 + 4 
3번째 년도 새롭게 분열된 1 + 1의 값만 필요 -> i-3-1
4번째 년도 새롭게 분열된 1 + 1 1 + 1 의 값만 필요 -> i-4-1

따라서 dp[i] -= (dp[i-4] + dp[i-5])

 

그리고 i=4일 경우를 체크하기 위해 추가로 dp[0]의 경우도 1로 초기화를 해주어야 한다.