[백준/C++]#11726 - 2xn 타일링

풀이

#include <iostream>

using namespace std;

int main() {
	int n;
	cin >> n;
    int D[1001];
	D[1]=1,D[2]=2;		// n=1, n=2일 때의 2xn 타일링 수
	for (int i=3; i<=n; i++) {	// n=3부터 n까지 반복
		D[i]=D[i-1]+D[i-2];
        D[i] %= 10007;		// 문제의 조건
	}
	cout << D[n];
	return 0;
}

개념

마찬가지로 다이나믹 프로그래밍 문제이다.

Bottom-Up 방식으로 순환호출을 사용하지 않고, 반복문을 사용해 문제를 해결했다.

---

풀이 

2xn의 타일링 경우의 수는 D[n]이다. 그리고 D[n]은 D[n-1] +D[n-2]이다.

이 두가지 경우가 2xn의 경우인데, 1x2 또는 2x1이 끝에 더해지기만 하므로 값은 그대로이다.

두 값을 더하기만 하면 된다,

따라서 피보나치수열과 동일한 문제나 다름없다.

 

---

+a

다음은 Top-down 방식을 사용한 해결책이다.

#include <iostream>

using namespace std;

int D[1001];
int tile(int k){
    if (k == 1) return 1;
    if (k == 2) return 2;
    if (D[k] > 0) return D[k];		// 배열에 값 저장되었으면 바로 출력
	D[k] = tile(k-1) + tile(k-2);
	D[k] %= 10007;
	return D[k];
}

int main() {
	int n;
	cin >> n;
	cout << tile(n);
	return 0;
}

if (D[k] > 0) return D[k]; 이 줄이 없으면 시간초과가 발생한다.

이를 사용한 중복제거가 생각보다 훨씬 중요한 것 같다.

 

이 방법 외에, 안타깝게도 처음 접근시 아주 복잡한 해결책을 생각했다.

2a + b = n으로 놓고, a와 b를 반복문을 통해 구한 뒤 그 값을 팩토리얼에 넣은 뒤, 모두 합해준다.

이론상으로는 가능하게 생각된다.

#include <iostream>

using namespace std;

int fact(int n){		// 팩토리얼 함수
	if (n < 2)
		return n;
	else
		return n * fact(n - 1);
}

int count(int x, int y) {		// count 함수
	return fact(x+y)/(fact(x)*fact(y));
}

int main() {
	int n, sum=0;
	cin >> n;
	int a = n/2, b = n % 2;
	for (; b <= n; a--,b+=2) {		// (a,b) 순서쌍을 뽑아냄
		sum += count(a,b);		// 각 순서쌍에 해당하는 경우를 모두 더함
	}
    cout << sum << '\n';
	return 0;
}

아래와 같이 구현했을 때, 런타임 에러가 나왔다. 팩토리얼을 반복문으로 바꿔도 마찬가지로 에러가 나타난다.

다이나믹 프로그래밍 방식처럼 이전 계산을 활용하지 않기 때문에 매우 많은 양의 계산을 시행해서 발생하는 문제로 추측된다. 

문제에 보다 쉽게 접근해야겠다!