[11726] 2xn 타일링

• 입력: 가로 길이 n(1,000 이하의 자연수)
• 출력: 2xn을 2x1 타일들로 표현할 수 있는 경우의 수를 10,007로 나눈 것
• 알고리즘: 동적계획법, 피보나치 수열
• 소스코드
#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <vector> using namespace std; vector<int> dp(1001, -1); int fibonacci(int n) { if (n == 0) return 1; else if (n == 1) return 1; else if (dp[n] != -1) return dp[n]; else return dp[n] = (fibonacci(n - 1) + fibonacci(n - 2) ) % 10007; } int main() { int n, t; scanf("%d", &n); printf("%d\n", fibonacci(n)); return 0; }

이 문제는 피보나치 수열로 풀 수 있다.

n = 1 일 때 세로 막대로 표현하는 경우 한 가지

n = 2 일 때 세로 막대 두 개로 표현하거나 가로 막대 두 개로 표현할 수 있어 두 가지

n = 3 일 때 n = 1에 n = 2를 붙이는 방법과 n = 2에 n = 1를 붙이는 방법 총 세 가지

n = 4 일 때 n = 2에 n = 2를 붙이는 방법과 n = 3에 n = 1를 붙이는 방법 총 다섯 가지

이런 식으로 가로 길이가 n일 때, (n - 2)에 세로 막대x2와 가로 막대x2를 붙여 표현할 수 있고, (n - 1)에 세로 막대를 하나를 붙여 표현할 수 있다. 즉 An = An-1+An-2인 피보나치 수열이다. 

• 문제 참고:https://www.acmicpc.net/problem/11726