Koala - 2기/C반
[25411633] 2×n 타일링 - 20200118(3)
알 수 없는 사용자
2021. 1. 18. 23:17
문제
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
풀이
더보기
n의 크기를 키워가며 방법의 수를 구하다 보면 피보나치 수의 규칙을 찾을 수 있다.
3번째 이후부터 Fn = Fn-1 + Fn-2 규칙을 적용할 수 있다.
따라서 0,1,2,3 번째까지의 vector는 초기화를 해준다.
그리고 vector의 크기가 기하급수적으로 커지는 것을 막기 위해 최종적으로 구해야하는 수인 2xn 크기의 직사각형을 채우는 방법의 수를 10007로 나눈 나머지를 저장한다.
소스코드
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
int N;
vector <long long> num;
int square(int a) {
if (a == N + 1)
return 0;
else {
if (a == 0 || a == 1 || a == 2 || a == 3)
num.push_back(a);
else
num.push_back(num[a - 1] + num[a - 2] % 10007);
}
square(a + 1);
return 0;
}
int main() {
cin >> N;
square(0);
cout << num[N] % 10007;
return 0;
}