[프로그래머스 Lv.2] 2 x n 타일링

문제는 다음과 같습니다.

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

프로그래머스

풀이 코드는 다음과 같습니다.

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int arr[60001]={0};
    int answer = 0;
    arr[0]=0;
    arr[1]=1;
    arr[2]=2;
    for(int i{3};i<=n;i++)
    {
        arr[i]=(arr[i-1]+arr[i-2])%1000000007;
    }
    answer=arr[n];
    return answer;
}

타일에 관한 문제로 보이지만 사실은 피보나치수열 문제입니다.

타일이 4개라면 타일이 2개일 때에 = (ㅡ 모양으로 2개)를 설치하거나 || (ㅣ 모양으로 2개)를 설치할 수 있고 타일이 3개일 때에 추가로 | 하나를 설치하는 경우의 수가 나오기 때문입니다. 이 부분은 피보나치 수열에서 주로 많이 사용되는 계단을 2칸 오르거나 1칸 오르는 문제와 유사합니다.

따라서 초기값을 설정해준 다음 입력받은 수 만큼 피보나치 수열을 진행하되, 문제 조건에 따라 1,000,000,007로 나눈 나머지를 return 해주어야 합니다.