[BOJ] 11726_2×n 타일링 with cpp

# 생각

테이블 정의

d[i] = 2 × i 크기의 직사강형을 채우는 방법의 수

 

점화식

2×1 타일로 덮으면 k-1가지

1×2 타일로 덮으면 k-2가지가 있기 때문에

d[k] = d[k-1] + d[k-2]가 된다

 

초기값

d[k]를 구할 때 k-2 까지 필요하므로 d[1]과 d[2]를 초기값으로 둔다

 

 

# 전체 코드

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

int d[1111];

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

	int n;
	cin >> n;
	d[1] = 1;
	d[2] = 2;
	for (int i = 3; i <= n; i++)
	{	// 마지막에만 나머지 연산으로 출력하게 되면 int 오버플로우가 날 수 있다
		d[i] = (d[i - 1] + d[i - 2]) % 10007;
	}
	cout << d[n];
}

 

---

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링