[C++] 백준 1309 [동물원]

나는 DP 문제들을 Top-down으로 푸는 것을 선호하고, 규칙을 찾아 점화식을 구성하기 보다 명확한 논리에 의해 구성되는 점화식을 선호한다.
이 문제에서 2가지 방법을 소개할 것인데, 개인적으로는 첫 번째 방법을 선호한다.

문제설명

2*N의 배열에 사자를 배치하는데, 사자를 연속된 배열에 위치시키는 것은 불가능하다.
이 때 우리를 구성하는 총 경우의 수는 얼마인가를 구하는 문제이다.
사자를 우리안에 배치하지 않는 경우도 포함된다.

풀이방법 1

처음에 이 문제를 보고, DP를 사용하는 문제인 것은 맞는데 overlapping subproblem을 어떻게 cache할 것인지 고민하였다.
점화식의 구성에 따라 cache 배열의 구조가 달라지기에 먼저 점화식을 어떻게 구성할 것인지 생각해보았다.
아래 그림은 점화식의 정의이다.

위의 정의에 따라 문제에서 구하고자 하는 총 경우의 수는 DP(0,N) + DP(1,N) + DP(2,N)이 된다.
각 항의 subproblem 구성 방식은 아래 그림과 같다.

위처럼 N번째 행이 비어있는 경우에는 N-1번째 행이 비어있거나, 왼쪽만 차있거나, 오른쪽만 차있는 경우 총 3가지가 가능하다.
그렇기에 DP(0,N) = DP(0,N-1) + DP(1, N-1) + DP(2, N-1) 이라는 점화식이 성립된다.

위처럼 N번째 행의 왼쪽만 차있는 경우, N-1번째 행이 비어있거나, 오른쪽만 차있는 경우 총 2가지가 가능하다.
그렇기에 DP(1,N) = DP(0,N-1) + DP(2, N-1) 이라는 점화식이 성립된다.

마지막으로, 위처럼 N번째 행의 오른쪽만 차있는 경우, N-1번째 행이 비어있거나, 왼쪽만 차있는 경우 총 2가지가 가능하다.
그렇기에 DP(2,N) = DP(0,N-1) + DP(1, N-1) 이라는 점화식이 성립된다.

위와 같이 명확한 점화식을 구성하였으므로, 이를 바탕으로 cache[3][100001] 이라는 메모이제이션 배열을 사용하여 Top-down으로 코드를 작성하겠다.

이 때 기저조건은 DP(0,1) = 1, DP(1,1) = 1, DP(2,1) = 1 이다.

소스코드 1

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

int cache[3][100001];

int dp(int a, int b){
    if(b == 1) return 1;
    int& ret = cache[a][b];
    if(ret != -1) return ret;
    if(a == 0){
        ret = dp(0,b-1) + dp(1, b-1) + dp(2,b-1);
    }
    if(a == 1){
        ret = dp(2,b-1) + dp(0, b-1);
    }
    if(a == 2){
        ret = dp(0,b-1) + dp(1, b-1);
    }
    ret = ret % 9901;
    return ret;
}

int main(){
    int N;
    cin >> N;
    memset(cache, -1, sizeof(cache));
    cout << (dp(0,N) + dp(1,N) + dp(2,N)) % 9901 << endl;
}

두 번째 방법은 메모이제이션 배열을 1차원 배열로 구성하는 방식이다.
이렇게 하면 코드는 더욱 간단해지지만, 첫 번째 방법을 모르고는 쉽게 점화식을 만들 수 없다.

풀이방법 2

이전 풀이 방법에서 사용하였던 정의를 이번 풀이 방법에서 사용한 정의로 바꾸는 과정이다.
점화식의 정의를 아래와 같이 바꿨다

DP(N)은 N번째 행에서 문제의 조건을 만족하는 경우의 수인데, 이는 이전 풀이방법의 정의에 따르면,
DP(N) = DP(0,N) + DP(1,N) + DP(2,N)과 같다.
이를 아래와 같이 식을 변형할 수 있다.

위 식은 또 아래와 같이 변형된다.

그러면 이제 DP(0,N-1)만 해결하면 된다.
이전 풀이방법의 정의에 따르면, DP(0,N-1) = DP(0,N-2) + DP(1,N-2) + DP(2,N-2)로 나타낼 수 있다.
이는 DP(N-2)와 동일하다.

그러므로 DP(N) = 2*DP(N-1) + DP(N-2)이다.

위와 같이 명확한 점화식을 구성하였으므로, 이를 바탕으로 cache[100001] 이라는 메모이제이션 배열을 사용하여 Top-down으로 코드를 작성하겠다.

이 때 기저조건은 DP(0) = 1, DP(1) = 3 이다.

소스코드 2

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

int cache[100001];

int dp(int a){
    if(a == 0) return 1;
    if(a == 1) return 3;
    int& ret = cache[a];
    if(ret != -1) return ret;
    ret = dp(a-1)*2+dp(a-2);
    ret = ret % 9901;
    return ret;
}

int main(){
    int N;
    cin >> N;
    memset(cache, -1, sizeof(cache));
    cout << dp(N) << endl;
}