[Level 3] 1. 2xN 타일링

1. 2xN 타일링

Algorithm - Level 3

- 풀이

1, n이 커지면서 갖는 경우의 수를 살펴본다.

- n=1 : 1

- n=2 : 2

- n=3 : 3

- n=4 : 5

- n=5 : 8

- n=6 : 13

.....

다음과 같이 n-1, n-2의 수의 덧셈이 n의 경우의 수를 생성하는 것을 볼 수 있다.

따라서, 이 또한 점화식을 이용하여 해결한다.

2, 단, 수가 커감에 따라, 자료형을 벗어날 수 있으며 문제에서 10000007로 나눈 나머지를 구하기로 하였으므로 덧셈 후 모듈러 연산이나, 최종값에 모듈러 연산이나 결과가 같기 때문에 덧셈 후 모듈러 연산을 한다.

#include <string>
#include <vector>
#include <iostream>
 
using namespace std;
 
int solution(int n) {
    int answer = 0;
 
    if(n==1) return 1;
    else if(n==2) return 2;
 
    vector<int> dp = {1, 2};
    for(int i=2; i<n; i++)
        dp.push_back((dp[i-1] + dp[i-2]) % 1000000007);
    
    answer = dp[n-1];
    
    return answer;
}