dp PS #boj 1309

문제

이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.

동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.

입력

첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.

출력

첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라

풀이1

(이차원) dp정의

dp[n][i] = 마지막 행의 케이스가 i일 때 지금까지 경우의 수의 최솟값

• 0 = 00
• 1 = 01
• 2 = 10

점화식

• dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2];
• dp[i][1] = dp[i-1][0] + dp[i-1][2];
• dp[i][2] = dp[i-1][0] + dp[i-1][1];

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define FASTIO   cin.tie(0);  cout.tie(0); ios_base::sync_with_stdio(0);

int dp[100001][3];

int main() {
    FASTIO;
    int N;
    cin >> N;

    dp[0][0] = 1;

    for (int i = 1; i <= N; ++i) {
        dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2];
        dp[i][1] = dp[i-1][0] + dp[i-1][2];
        dp[i][2] = dp[i-1][0] + dp[i-1][1];
        for (int j=0; j<3; j++) {
            dp[i][j] %= 9901;
        }
    }

    cout << (dp[N][0] + dp[N][1] +dp[N][2]) % 9901;
}

풀이2

dp의 정의

dp[i] : i번째에 동물이 있을 때, 2*i를 채우는 방법의 수
s[i] : dp의 부분합 수열 정의.

dp점화식

dp[i] = dp[i-1] + 2*s[i-2];

case1. i-1번째에 동물을 배치하는 경우.

i번째와 크로스로 배치되어야 하기에, 동물의 위치가 자동으로 지정됨.
따라서 그 경우의 수는 dp[i-1]과 동일

case2. i-1번째에 동물을 배치하지 않는 경우.

i번째에 동물을 배치하는 경우의 수는 2가지이고,
이 각각의 경우 마다 dp[k] : k는 1 ~ (i-2)가 가능하기에
경우의 수는 2(dp[i-2]+...+dp[2]+dp[1]) = 2 * s[i-2]

참고

dp[0]과 s[0]을 1로 설정하는 것은, "아무것도 없는 상태"에서 시작하여 문제의 해를 단계적으로 구축해 나가는 과정의 시작점

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define FASTIO   cin.tie(0);  cout.tie(0); ios_base::sync_with_stdio(0);
int dp[100001];
int s[100001]; //d의 부분합 수열

int main() {
    FASTIO;
    int n;
    cin >> n;

    dp[0] = 1; dp[1] = 2;
    s[0] = 1; s[1] = dp[0] + dp[1];
    
    for (int i=2; i<=n; i++) {
        dp[i] = dp[i-1] + 2*s[i-2];
        s[i] = s[i-1] + dp[i];
        
        dp[i] = dp[i] % 9901; s[i] = s[i] % 9901;
    }
    cout << s[n] << '\n';
    return 0;
}