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

programmers.co.kr/learn/courses/30/lessons/12900?language=java#

문제 해석

높이가 2이고 길이가 N 인 공간이 있을때
가로가 1이고 세로가 2인 타일을 이용해서 공간을 채우는 경우의수를 구해라

 

문제 풀이

처음에는 조합으로 푸는 문제인줄 알았는데
조금만 생각해보면 간단하게 풀 수 있었다

n이 순차적으로 증가할때
1, 2, 3, 5, 8, 13, 21 ....

n을 채우는 경우의 수는 피보나치 순으로 증가한다는 것!!

경우의 수가 너무 커지는 경우 오버플로우를 피하기 위해 나머지연산을 먼저 하는것만 주의

 

  class Solution {
    public int solution(int n) {
        int answer = 0;

        if(n == 0) return 0;

        int temp1 = 0;
        int temp2 = 1;

        for(int i = 2; i <= n; i++)
        {
            if(i % 2 == 0) temp1 = (temp1 + temp2) % 1000000007;
            else temp2 = (temp1 + temp2) % 1000000007;
        }
        answer = (temp1 + temp2) % 1000000007;

        return answer;
    }
}