백준(C) 11727번 2xn 타일링2 풀이

C로 구현한 2752번 2xn 타일링2 문제 풀이입니다.

 

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

11727번: 2×n 타일링 2

---

이 문제의 규칙성을 찾기 위해서 아래의 글을 참고하시면 좋을거 같습니다.

https://unie2.tistory.com/40?category=875841 

백준(C) 11726번 2xn 타일링 풀이

 

다이나믹 프로그래밍(DP; Dynamic Programming) 과정

문제에서 n이 2일 때는 가로로 긴 타일 2개를 붙여서 채우는 방법 하나와 세로로 긴 타일 2개를 붙여서 채우는 방법

 

하나, 그리고 2x2 타일로 채우는 방법 하나로 총 3가지 이다.

 

만약 이미 많은 타일이 채워져 있고 2개의 타일을 추가하고자 할 때 세로로 긴 타일을

 

 

추가하는 것은 타일을 1개 추가하고자 할 때에 포함되기 때문에 가로로 긴 타일을 추가하는 것과

 

2x2 타일을 하나 추가하는 것만 방법의 수로 생각한다.

 

최종적으로 결국 이 문제의 규칙은 D[n] = D[n-1] + 2*D[n-2] 를 만족한다.

#include <stdio.h>

int n[1001];

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

int main() {
	int x;
	scanf("%d", &x);
	printf("%d", dp(x));
}

 

메인코드에서 x를 입력하여 함수 dp에 전달한다. x가 1일 때 타일을 채우는 방법의 수는 1가지이기 때문에 1을 반환한다.

 

x가 2일 때 타일을 채우는 방법의 수는 3가지이기 때문에 3을 반환한다.

 

시스템이 효율적으로 동작하기 위해 계산한 결과를 배열에 저장함으로써 이후 동일한 계산을 해야할 때 저장된 값을

 

반환하는 방식을 사용한다. 만약 n[x]의 값이 이미 존재한다면 그 값을 반환하고 그렇지 않을 경우에는

 

D[n-1] + 2*D[n-2]를 만족하도록 계산해준 뒤, 문제에서 요구하는 10007의 나머지 값을 반환하여 출력한다.