2 x n 타일링

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

프로그래머스

 

막대기의 가로 길이가 2, 세로 길이가 1 이므로,

 

길이 n인 직사각형을 만들기 위해서는

 

n-1 길이의 직사각형에 막대기를 세로로 붙이는 방법 + n - 2 길이의 직사각형에 막대기를 가로로 붙이는 방법이 있다.

 

결국 피보나치를 이용해 풀면 됨을 알 수 있다.

 

 

import java.util.*;

class Solution {
    
    final int divide = 1_000_000_007;
    
    public int solution(int n) {
        
        int[] arr = new int[n];
        arr[1] = 2;
        arr[2] = 3;
        
        for (int i = 3; i < n; i++) {
            arr[i] = (arr[i - 1] + arr[i - 2]) % divide;
        }
        
        return arr[n - 1];
    }
}