[ 프로그래머스 ] 2 X N 타일링

문제

---

https://school.programmers.co.kr/learn/courses/30/lessons/12900

풀이

---

가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일을 N X 2 사각형에 배치할 때, 배치할 수 있는 경우의 수를 구하는 문제로, 다음 사이즈의 경우의 수가 이전 사이즈의 경우의 수에 영향을 받으므로 DP를 활용, 점화식을 세워 풀이하였다.

#include <string>
#include <vector>

using namespace std;

int arr[60000];

int solution(int n) 
{
    int answer = 0;

    //1 1 2 2 3 3 4 5

    arr[0] = 1;
    arr[1] = 2;

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

    answer = arr[n - 1];

    return answer;
}