[백준 11726번/c++] 2*n 타일링

알고리즘

 

• 다이나믹 프로그래밍

 

---

풀이

타일은 |  또는 ㅡ  같은 모양을 가진다.

 

직사각형 2*n에서 n이 하나 증가하면

 

• 열이 한칸 더 생기는 것으로 | 만큼이 더 생기게 된다. 그러므로 2*n-1을 채우는 방법에 | 을 붙여주면 된다.

 

이 외의 경우의 수가 하나 더있는데

• = 가로 두개가 마지막에 붙는 경우이다. 이 경우에는 2*n-2을 채우는 방법에 = 을 붙여주면 된다.

즉 직사각형 2*n을 채우는 방법의 수는 2*n-1을 채우는 방법의 수 + 2*n-2을 채우는 방법의 수가 된다.

 

벡터 dy를 이용하여 나타낼 수 있다.

• dy[1]은 | 로 채울 수 있는 방법이 하나이므로 1으로 초기화
• dy[2]는 || 또는 = 로 채울 수 있는 방법이 두가지이므로 2로 초기화 한다.

dy[1]=1
dy[2]=2
dy[n]=dy[n-1]+dy[n-2] (n>=3)

 

---

⚠️ 주의할 점

문제에서는 2*n 크기의 직사각형을 채우는 방법의 수를 10007로 나눈 나머지를 출력하도록 하고 있는데,

dy 값을 모두 구한 후 dy[n]%10007을 해주게 되면 오버플로우가 될 수 있어 예상과 다른 값이 나올 수 있다.

따라서 dy 배열의 값을 구하며 %10007을 해주어야 한다.

 

---

성공 코드

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

int main() {
   freopen("input.txt", "rt", stdin);
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   cout.tie(NULL);
   
   int n;
   cin >> n;
   vector<int> dy(n+1, 0);
   dy[1]=1;
   dy[2]=2;
   for(int i=3; i<=n; i++){
      // 오버플로우 일어날 수 있으므로 10007을 나눠서 저장해줘야 한다. 
      dy[i]=(dy[i-1]+dy[i-2])%10007;
   }
   cout << dy[n];
   
   return 0;
}