[백준] 11726번: 2 x n 타일링 (C언어)

 

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

11726번: 2×n 타일링

난이도: solved.ac 실버 3

 

대표적인 다이나믹 프로그래밍 알고리즘 문제다

우선 길이가 1일 때는 아래와 같이 세로로 세우는 방법 딱 한 가지만 존재한다

 

길이가 2일 때는 아래와 같이 두 가지만 존재한다

 

 

 

그리고 더 나아가 가로의 길이가 N인 상태를 보자

 

여기서 한 칸을 추가시키려면 아래의 방법 밖에 없다

 

 

그리고 두 칸을 추가시키기 위해서는 아래의 방법만 존재한다

 

아래의 방법은 길이가 N일 때 하나를 더 추가시키고 하나를 더 추가시키는 것과 겹치기 때문이다

 

따라서 점화식은 아래와 같이 나온다

 

 

이를 코드로 나타내면 아래와 같다

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int arr[1001] = { 0,1,2 };
int main() {
	int n, i;
	scanf("%d", &n);
	for (i = 3; i <= n; i++)
		arr[i] = (arr[i - 1] + arr[i - 2]) % 10007;
	printf("%d", arr[n]);
	return 0;
}