[algospot] 폴리오미노 (c++)

풀이 방법

dp 문제인데 문제를 부분 문제로 나누기 어려운 문제 였다.

처음에는 정사각형 하나를 두고 상하좌우로 사각형을 붙이는 형태로 부분 문제를 쪼개려고 생각 했지만 이러면 중복되는 부분을 다 제거 하기가 복잡해서 실패 했다.

정답은 층별로 부분 문제를 쪼개는 것이다 재귀 함수로 현재 남은 상자수와 각 재귀마다 첫 층에 쓸 상자수를 보내주고 

함수 안에서 for 문을 돌며 2번째 층에는 몇개의 상자를 사용할지 선택후 함수 리턴값을 더하면 된다

여기서 리턴값에 first + second - 1를 곱해주어야 한다 1층과 2층을 한 칸씩 옆으로 이동시키면 다른 경우가 되기 때문이다. 시간 복잡도는 O(n^3)이다.

#include <iostream>
#include <algorithm>
#include <memory.h> 
#include <vector>

const int MOD = 10000000;
using namespace std;

int dp[101][101];

int f(int n, int first) {
    if (n == first) return 1;
    int& ret = dp[n][first];
    if (ret != -1) return ret;
    ret = 0;
    for (int i = 1; i <= n - first; i++) {
        int add = i + first - 1;
        add *= f(n - first, i);
        add %= MOD;
        ret += add;
        ret %= MOD;
    }
    return ret;
}

int main(void) {
    int C;
    cin >> C;        
    while (C--) {
    	memset(dp, -1, sizeof(dp));
        int num;
        cin >> num;
        int count = 0;
        for (int i = 1; i <= num; i++) {
            count += f(num, i);            
            count %= MOD;
        }
        cout << count << endl;
    }
    return 0;
}