> [!date] published: 2022-02-07
[11726번: 2×n 타일링](https://www.acmicpc.net/problem/11726)
## 🌟 문제
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
## 🌟 입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
## 🌟 출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
## 🌟 풀이
사실 동일한 문제를 예전에 풀어 본 적이 있어서 점화식은 금방 생각해 낼 수 있었다.
일단 뭔가 일정한 규칙이 있어 보이니 그려보기로 했다.
![[31ee8325-248c-4457-9e15-758e7435ebcf.png]]
도형도구로만 그린거라 좀 허접하지만; 2×n 크기의 직사각형을 만드는 방법에 2×(n-1) 크기의 직사각형을 만드는 방법과 2×(n-2) 크기의 직사각형을 만드는 방법이 포함되어 있는 것을 알 수 있다. 따라서 다이나믹 프로그래밍을 위한 점화식은 2×n 크기의 직사각형을 만드는 방법을 dp\[n\]이라고 하면 **dp\[n\] = dp\[n-1\] + dp\[n-2\] (dp\[1\] = 1, dp\[2\] = 2)** 라고 세울 수 있다.
그래서 dp\[3\]부터 시작해서 dp\[n\]까지 반복문을 돌며 dp 배열을 채워주면 되는데... 주의할 점은 더한 값들을 그대로 넣어주면 정수 범위를 벗어나게 되어 틀린 값이 나온다! 문제에서 요구한 대로 10,007로 나누어준 나머지를 배열에 넣어주자.
이게 가능한 이유는 모듈러 연산의 분배법칙 때문이다.
- (A + B) % p = ((A % p) + (B % p)) % p
- (A \* B) % p = ((A % p) \* (B % p)) % p
- (A - B) % p = ((A % p) - (B % p) + p) % p
## 🌟 코드
```cpp
/*
2022-2-7
11726_2×n 타일링
https://www.acmicpc.net/problem/11726
*/
#include <iostream>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
int dp[1001];
cin >> n;
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];
return (0);
}
```