[백준 1648] 격자판 채우기 (C#, C++) - soo:bak

문제 링크

1648번 - 격자판 채우기

설명

N×M 격자를 2×1 도미노로 빈틈없이 채우는 경우의 수를 9901로 나눈 값을 구하는 문제입니다. 도미노는 가로 또는 세로로 놓을 수 있습니다.

접근법

격자를 왼쪽 위부터 오른쪽 아래로 한 칸씩 채워나갑니다. 현재 위치와 그 칸 이후로 영향을 주는 점유 상태를 비트마스크로 관리합니다. 비트마스크는 현재 칸부터 M칸에 대해 이미 채워졌는지를 나타냅니다.

현재 칸이 이미 채워져 있다면 다음 칸으로 넘어갑니다. 비어 있다면 도미노를 가로 또는 세로로 놓을 수 있습니다. 가로로 놓으려면 오른쪽 칸도 비어 있어야 하고, 열의 끝이 아니어야 합니다. 세로로 놓으면 현재 칸을 채우고 아래 칸에 해당하는 비트를 표시합니다.

모든 칸을 채웠을 때 비트마스크가 0이면 성공적으로 채운 것이고, 그렇지 않으면 불가능한 경우입니다. 메모이제이션을 사용하여 중복 계산을 방지합니다.

---

Code

C#

using System;

class Program {
  const int MOD = 9901;
  static int n, m;
  static int[,] dp = new int[14 * 14 + 1, 1 << 14];

  static int Solve(int pos, int mask) {
    if (pos == n * m) return mask == 0 ? 1 : 0;
    var cached = dp[pos, mask];
    if (cached != -1) return cached;

    var res = 0;
    if ((mask & 1) != 0) {
      res = Solve(pos + 1, mask >> 1);
    } else {
      var col = pos % m;
      if (col < m - 1 && (mask & 2) == 0)
        res = (res + Solve(pos + 2, mask >> 2)) % MOD;
      res = (res + Solve(pos + 1, (mask >> 1) | (1 << (m - 1)))) % MOD;
    }
    dp[pos, mask] = res;
    return res;
  }

  static void Main() {
    var parts = Console.ReadLine()!.Split();
    n = int.Parse(parts[0]);
    m = int.Parse(parts[1]);
    for (var i = 0; i < dp.GetLength(0); i++)
      for (var j = 0; j < dp.GetLength(1); j++)
        dp[i, j] = -1;

    Console.WriteLine(Solve(0, 0));
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;

const int MOD = 9901;
int n, m;
vvi dp;

int solve(int pos, int mask) {
  if (pos == n * m) return mask == 0 ? 1 : 0;
  int &ret = dp[pos][mask];
  if (ret != -1) return ret;
  int res = 0;
  if (mask & 1) {
    res = solve(pos + 1, mask >> 1);
  } else {
    int col = pos % m;
    if (col < m - 1 && (mask & 2) == 0)
      res = (res + solve(pos + 2, mask >> 2)) % MOD;
    res = (res + solve(pos + 1, (mask >> 1) | (1 << (m - 1)))) % MOD;
  }
  return ret = res;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> m;
  dp.assign(n * m + 1, vi(1 << m, -1));
  cout << solve(0, 0) << "\n";

  return 0;
}