(백준BAEKJOOB )- 11726번 -2xn 타일링 문제 "c"

 

이 문제를 풀기 위해서 dp 라는 알고리즘을 공부했고

파보나치 수를 공부했다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

앞에 수와 더하는 것이다. 

 

 

한마디로 

이것을 구하기 위한 점화식은

d[x]=d(x-1)+d(x-2)로 볼수있다.

int a[1001];
int dp(int x) {
	if (x == 1) return 1; //타일 한개 일때는 한개만
	if (x == 2) return 2; //타일 2개일때 3가지 나옴 

	if (a[x] != 0) {
		return a[x];
	}
	return a[x] = ((dp(x - 1) + dp(x - 2))) % 10007;
}

코드를 보면 배열을 1000까지 하고 
x==1이면 1개 타일이 1개일 때 1개가 나오기 때문에 1 반환
x==2이면  타일이 2개일 때 2개의 타일이 나오기 때문에 2 반환

 

	if (a[x] != 0) {
		return a[x];
	}

 

이걸 빼도 코드가 돌아 가긴하지만 a[x]!=0이 아닐때만 돌아가게 해야 메모리가 절약된다.

만약1001까지 다 돌아가면 그만큼 시간이 많이 걸리기 때문에

 

이문제를 이용해서 2xn 타일링 문제 2도 풀면(https://www.acmicpc.net/problem/11727)

 

    return a[x] = ((dp(x - 1) + 2 * dp(x - 2))) % 10007;

이풀이만 추가하면된다.

 

이유는 사각형의 경우에 따라 x-2인 경우가 두번있으니 2만 곱하면 된다.

 

 

 

 

 

 

 

총 코드

---

 

 

#include<stdio.h>

int a[1001];
int dp(int x) {
	if (x == 1) return 1; //타일 한개 일때는 한개만
	if (x == 2) return 2; //타일 2개일때 3가지 나옴 

	if (a[x] != 0) {
		return a[x];
	}
	return a[x] = ((dp(x - 1) + dp(x - 2))) % 10007;
}



int main() {
	int n;
	scanf_s("%d", &n);
	printf("%d", dp(n));
}