2 x n 타일링

#include <string>
#include <vector>
 
using namespace std;
 
int solution(int n) {
    int i, tale[60000];
    tale[0] = 0;
    tale[1] = 1;
    tale[2] = 2;
    
    for(i = 3; i <= n; i++) {
        tale[i] = (tale[i - 1] + tale[i - 2]) % 1000000007;
    }
    return tale[n];
}

다 풀어놓고도 왜 틀렸는지 몰랐던 문제. 각각의 배열에 더해줄때 1000000007로 나눈 나머지를 저장했어야했다.

이 문제는 거꾸로 생각해보면 피보나치 수열과 같은 문제임을 알 수 있다.

예를 들어, n 길이의 타일이 주어졌다고 할 때 그중 1개의 타일을 뒤에서 뺴면 (n-1)개로 이뤄진 타일이다. 그리고 뒤에서 2개를 뺴면 (n-2)개로 이뤄진 타일이다. 3개를 빼나 1개를 빼고 2개를 뺀 것의 케이스를 더해주나 같으므로 n 길이의 타일은 (n-1) + (n-2)의 타일들의 경우의 수를 합한 것으로 이뤄져 있음을 알 수 있다.

그래서 배열 하나를 선언해주고 피보나치 수열을 계산할 때 처럼 반복문을 반복해주면 된다. 

더해줄 때 꼭!! 나눠서 할당을 해줘야함을 잊지 말자.