[DP] 백준 11726: 2*n 타일

https://www.acmicpc.net/problem/11726

 

타일을 맞춘다고 표현했지만 결국 문제에서 요구하는 것은

 

'1과 2를 나열하여 n을 맞추는 경우의 수' 일 것이다. 가로가 2인짜리 블럭을 사용하면 그 아래도 꼼짝없이 같은 블럭으로 채워야지, 다른 경우가 있을 수 없기 때문이다.

 

맨 처음에 재귀함수를 이용한 시도에서는 (예제의) 정답은 다 맞췄지만 시간 초과가 났다. 그래서 시간을 줄이기 위해 memoization을 사용하기로 했다.

 

먼저 n=1인 경우는 ㅣ 한 가지 경우의 수밖에 없고, n=2인 경우는 ㅡ 한 가지 경우의 수밖에 없다면,

n=3인 경우 ㅣㅣㅣ,ㅣㅣㅡ, ㅣㅡㅣ,ㅡㅣㅣ 4 가지 수가,

n=4인 경우, ㅣㅣㅣㅣ,ㅡㅡ,ㅣㅣㅡ,ㅣㅡㅣ,ㅢㅣ 5가지 수가 존재한다. 

 

여기서 f(n) = f(n-1)+f(n-2) 라는 공식을 유추하고 다음과 같은 코드를 이용하여 해결하였다.

#include <iostream>
#include <vector>
using namespace std;



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin>>n;

    int answer = 0;

    vector<int> memoization(n, 0);

    memoization[0] = 1;
    memoization[1] = 2;

    for(int i=2;i<n;i++)
    {
        memoization[i] = (memoization[i-1]+memoization[i-2])%10007;
    }

    cout<<memoization[n-1];
}