[C++] 백준 11726번 2xn 타일링

피보나치 수열을 이용해서 풀었습니다.

1 - 1

2 - 2

3 - 3

4 - 5

5 - 8

6 - 13

.....

 

n번째를 구할때 n-1과 n-2를 더해서 구할 수 있습니다.

차례대로 밑에서부터 값을 구하면서 memo에 값을 저장해두고

그 값을 통해 다음 숫자를 풀어나가는 방식입니다.

다이나믹 프로그래밍방식 입니다.

 

#include  
using namespace std; 

int memo[1001]; 
int x; 

void func(int num) 
{ 
    if (num <= x) { 
        memo[num] = memo[num - 2] + memo[num - 1]; 
    memo[num] %= 10007; 
    func(++num); 
    } 
    return; 
} 

int main(int argc, char *argv[]) 
{ 
    memo[0] = 1; 
    memo[1] = 1; 
    memo[2] = 2; 
    cin >> x; 
    func(3); 

    memo[x] %= 10007; 
    cout << memo[x]; 
    return 0; 
}