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

C로 구현한 2752번 세수정렬 구하기 문제 풀이입니다.

 

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

11726번: 2×n 타일링

---

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

 

문제에서 n이 1일 때 1x2 혹은 2x1 타일로 채우는 방법의 수는 1가지 이다.

 

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

 

총 방법의 수는 2가지 이다.

 

n이 3일 때의 방법의 수는 3이며, 만약 이미 많은 타일이 채워져 있고 2개의 타일을 추가하고자 할 때 세로로 긴 타일을

 

추가하는 것은 타일을 1개 추가하고자 할 때에 포함되기 때문에 가로로 긴 타일을 추가하는 것만 방법의 수로 생각한다.

 

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

#include <stdio.h>

int n[1001];

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

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

 

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

 

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

 

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

 

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

 

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