[Programmers] Level2 : 2 x n 타일링

Question

---

Solution

• 완성된 직사각형의 마지막 가로의 길이가 1일때 f(n-1)
• 완성된 직사각형의 마지막 가로의 길이가 2일때 f(n-2)
• 점화식: n > 2, f(n) = f(n-1) + f(n-2)
• 경우의 수가 많기 때문에 dp를 활용하여 풀었다.

---

Cord

#include <string>
#include <vector>

using namespace std;

int dp[60001];

// 점화식 : n > 2, f(n) = f(n-1) + f(n-2) 
int tiles(int n)
{
    if (n == 1) { return 1; }
    else if (n == 2) { return 2; }
    
    if (dp[n] != 0) { return dp[n]; }
    
    return dp[n] = (tiles(n-1) + tiles(n-2)) % 1000000007;
}

int solution(int n) 
{
    int answer = 0;
    answer = tiles(n); 
    return answer;
}

---

Result