BOJ 11726 2xn 타일링

문제출처 : https://www.acmicpc.net/problem/11726

1. 문제요약

- 2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수는?

- 1 <= n <= 1,000

- 10007로 나눈 나머지를 출력

2. 접근방법

- 2xn 도형을 채우는데 n번째에 올 수 있는 모형의 종류는

  세로 1x2 1개

  가로 2x1 2개

  가 올 수 있음

- d[n]을 2xn 모형을 채우는 경우의 수 라고 하면

  d[n] = d[n-1] + d[n-2]

  피보나치

3. 시간복잡도

- n

4. 회고

- 모듈러 연산 : https://ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-addition-and-subtraction

소스코드

#include<iostream>
using namespace std;

int n, d[1001] = { 0, 1, 2 };

int main(void){
	cin >> n;
	for (int i = 3; i < n + 1; i++){
		d[i] = d[i - 2] + d[i - 1];
		d[i] %= 10007;
	}
	cout << d[n] << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]