콘텐츠로 이동

깨진 프로필 위의 동적 계획법. 문제 "Parquet"

깨진 프로필 DP로 해결하는 대표적인 문제는 다음과 같습니다.

  • 어떤 영역(예: 체스판/격자)을 특정 도형(예: 도미노)으로 완전히 채우는 방법의 수 구하기
  • 최소 개수의 도형으로 영역을 채우는 방법 구하기
  • 채워지지 않은 공간(격자의 경우 칸)이 최소가 되도록 부분적으로 채우는 방법 구하기
  • 더 이상 도형을 추가할 수 없으면서 도형의 개수가 최소가 되도록 부분적으로 채우는 방법 구하기

문제 "Parquet"

문제 설명. 크기가 $N \times M$인 격자가 주어집니다. 크기가 $2 \times 1$인 도형으로 격자를 채우는 방법의 수를 구하십시오(채워지지 않은 칸이 남아서는 안 되며, 도형끼리 겹쳐서도 안 됩니다).

DP 상태를 $dp[i, mask]$로 정의합니다. 여기서 $i = 1, \ldots N$이고 마스크 $mask = 0, \ldots 2^M - 1$입니다.

$i$는 현재 격자의 행 수를 나타내고, 마스크 $mask$는 현재 격자의 마지막 행의 상태입니다. 마스크 $mask$의 $j$번째 비트가 $0$이면 해당 칸은 채워져 있고, 그렇지 않으면 비어 있습니다.

문제의 답은 분명히 $dp[N, 0]$입니다.

각 $i = 1, \cdots N$과 각 마스크 $mask = 0, \ldots 2^M - 1$을 순회하며 DP 상태를 구성하고, 각 마스크 $mask$에 대해 앞으로만 전이합니다. 즉, 현재 격자에 도형을 추가하는 방식으로 진행합니다.

구현

int n, m;
vector < vector<long long> > dp;


void calc (int x = 0, int y = 0, int mask = 0, int next_mask = 0)
{
    if (x == n)
        return;
    if (y >= m)
        dp[x+1][next_mask] += dp[x][mask];
    else
    {
        int my_mask = 1 << y;
        if (mask & my_mask)
            calc (x, y+1, mask, next_mask);
        else
        {
            calc (x, y+1, mask, next_mask | my_mask);
            if (y+1 < m && ! (mask & my_mask) && ! (mask & (my_mask << 1)))
                calc (x, y+2, mask, next_mask);
        }
    }
}


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

    dp.resize (n+1, vector<long long> (1<<m));
    dp[0][0] = 1;
    for (int x=0; x<n; ++x)
        for (int mask=0; mask<(1<<m); ++mask)
            calc (x, 0, mask, 0);

    cout << dp[n][0];

}

연습 문제

참고 문헌