1904번 01타일

문제링크 : www.acmicpc.net/problem/1904

1904번: 01타일

---

---

<알고리즘>

 00과 1로 만들 수 잇는 조합 결과를 생각하기 보단 그 조합의 갯수를 생각해야함 

 1) N이 0개인경우, 1개인경우, 2개인 경우를 미리 계산해 배열에 넣어둠

 2) 그리고 N번째까지 배열의 값을 구하기

 3) 배열의 N번째 값 출력

 

 

 

버전 1. 재귀함수 사용 (시간초과)

#include <iostream>
#include <vector>
using namespace std;

long long inttile(int n) {
	if (n == 0) return 0;
	else if (n == 1) return 1;
	else if (n == 2) return 2;
	else {
		return tile(n - 1) + tile(n - 2);
	}
}
int main() {
	int N = 0;
	cin >> N;
	cout << tile(N)%15746 << "\n";
	return 0;
}

 

 

 

 

버전 2. 피보나치 수열 방식 차용(시간 : 20460KB  메모리 : 16ms)

N=0		0가지
N=1	1	1가지
N=2	00, 11	2가지
N=3	001, 100, 111	3가지
N=4	0000, 0011, 1100, 1111	4가지
N=5	00001, 10000, 11100, 11001, 10011, 00111, 11111	7가지

#include <iostream>
#include <vector>
using namespace std;

vector<long long int> dt = { 0,1,2 };
void tile(int n) {
	for (int i = 3; i <= n; i++) {
		dt.push_back((dt[i - 1] + dt[i - 2]) % 15746);
	}
}
int main() {
	int N = 0;
	cin >> N;
	tile(N);
	cout << dt[N]%15746 << "\n";
	return 0;
}