[백준 2133] 타일 채우기 (C#, C++) - soo:bak

문제 링크

2133번 - 타일 채우기

설명

3 × N 크기의 벽이 주어지는 상황에서, N (1 ≤ N ≤ 30)이 주어질 때, 2 × 1과 1 × 2 크기의 타일로 벽을 채우는 경우의 수를 구하는 문제입니다.

N이 홀수인 경우 3 × N 벽의 총 칸 수가 홀수가 되어 크기 2인 타일로는 완전히 채울 수 없으므로 경우의 수는 0입니다. N이 짝수인 경우에만 채울 수 있습니다.

접근법

동적 프로그래밍으로 경우의 수를 계산합니다. dp[i]를 3 × i 크기의 벽을 채우는 경우의 수라고 정의합니다.

기본 경우로 dp[0] = 1 (빈 벽), dp[2] = 3입니다. 3 × 2 벽은 3가지 방법으로 채울 수 있습니다.

i ≥ 4인 짝수에 대해, dp[i]는 두 부분으로 나뉩니다.

첫째, 오른쪽 끝 3 × 2 영역을 3가지 기본 패턴으로 채우고 나머지 3 × (i-2) 영역을 채우는 경우: dp[i-2] × 3

둘째, i-4, i-6, …, 0 각 위치에서 새로운 특수 패턴(각 2가지)이 생기는 경우: 2 × (dp[i-4] + dp[i-6] + … + dp[0])

따라서 점화식은 dp[i] = dp[i-2] × 3 + 2 × (dp[i-4] + dp[i-6] + … + dp[0])입니다.

N이 최대 30으로 작으므로 이중 반복문으로 충분히 빠르게 계산할 수 있습니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var n = int.Parse(Console.ReadLine()!);
      
      if (n % 2 == 1) {
        Console.WriteLine(0);
        return;
      }

      var dp = new int[n + 1];
      dp[0] = 1;
      dp[2] = 3;
      
      for (var i = 4; i <= n; i += 2) {
        dp[i] = dp[i - 2] * 3;
        for (var j = i - 4; j >= 0; j -= 2)
          dp[i] += dp[j] * 2;
      }
      
      Console.WriteLine(dp[n]);
    }
  }
}

C++

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

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

  int n;
  cin >> n;
  
  if (n % 2 == 1) {
    cout << 0 << "\n";
    return 0;
  }
  
  vector<int> dp(n + 1, 0);
  dp[0] = 1;
  dp[2] = 3;
  
  for (int i = 4; i <= n; i += 2) {
    dp[i] = dp[i - 2] * 3;
    for (int j = i - 4; j >= 0; j -= 2)
      dp[i] += dp[j] * 2;
  }
  
  cout << dp[n] << "\n";
  
  return 0;
}