[백준 11726] 2×n 타일링 (C#, C++) - soo:bak

문제 링크

11726번 - 2×n 타일링

설명

2 × n 크기의 직사각형을 1 × 2와 2 × 1 타일로 채우는 방법의 수를 구하는 문제입니다.

결과는 10,007로 나눈 나머지를 출력합니다.

접근법

동적 프로그래밍을 사용하여 해결합니다.

2 × n 직사각형의 오른쪽 끝을 채우는 방법은 두 가지입니다.

2 × 1 타일을 세로로 하나 놓으면 남은 부분은 2 × (n - 1) 크기가 되고,

1 × 2 타일을 가로로 두 개 쌓으면 남은 부분은 2 × (n - 2) 크기가 됩니다.

따라서 dp[n] = dp[n - 1] + dp[n - 2]의 점화식이 성립합니다.

기저 값은 dp[1] = 1, dp[2] = 2로 설정하고, n까지 반복적으로 계산합니다.

각 단계에서 10,007로 나눈 나머지만 저장하여 오버플로우를 방지합니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var n = int.Parse(Console.ReadLine()!);
      var dp = new int[Math.Max(3, n + 1)];
      dp[1] = 1;
      dp[2] = 2;

      for (var i = 3; i <= n; i++)
        dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;

      Console.WriteLine(dp[n]);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;

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

  int n; cin >> n;

  vi dp(max(3, n + 1));
  dp[1] = 1;
  dp[2] = 2;
  for (int i = 3; i <= n; ++i)
    dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;

  cout << dp[n] << "\n";

  return 0;
}