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

문제

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

프로그래머스

 

풀이

점화식은 f(n) = f(n-1)+f(n-2) 으로 나타난다.

 

길이 n인 바닥의 맨 앞에 새로로 타일을 하나 놨다고 생각하자. 그럼 남은 길이는 N-1이 된다. 그러므로 남은 공간을 채우는 가지수는 f(n-1)이 된다.

반대로 타일을 가로로 놨다고 생각해보자. 타일을 가로로 놨다면 남은 길이는 n-2가 된다. 그러므로 남은 공간을 채우는 가지수는 f(n-2)이다.

이 두 경우를 합 한것이 길이 n의 경우의 수가 된다.

 

코드

class Solution {
    public int solution(int n) {
        int arr [] = new int [n+1];
        arr[1] = 1;
        arr[2] = 2;
        for(int i=3;i<=n;i++){
            arr[i] = (arr[i-1] + arr[i-2])%1000000007;
            // System.out.println(arr[i]);
        }
        
        return arr[n];
    }
}