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

programmers.co.kr/learn/courses/30/lessons/12900

[

코딩테스트 연습 - 2 x n 타일링

가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는

programmers.co.kr

](https://programmers.co.kr/learn/courses/30/lessons/12900)

처음에는 동적계획법을 이용해 풀고자 했으나 시간초과가 떠벼렸다

그 후 규칙성을 찾아보고자 고민한 결과 n에따른 피보나치 수열이 결정됨을 알아냈다

아래를 확인해보자

n = 0 일경우의 타일배치의 경우의 수는 0

n = 1 일경우의 타일배치의 경우의 수는 1

n = 2 일경우의 타일배치의 경우의 수는 2

n = 3 일경우의 타일배치의 경우의 수는 3

n = 4 일경우의 타일배치의 경우의 수는 5

n = 5 일경우의 타일배치의 경우의 수는 8

class Solution {

    public int solution(int n) {
        if(n<=1){return n;}
        int[] fibo = new int[n+2];
        fibo[0] = 0;
        fibo[1] = 1;
        for(int i =2;i<n+2;i++){
            fibo[i] = (fibo[i-1] + fibo[i-2])%1000000007;
        }

        return fibo[n+1]%1000000007;
    }



}