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

문제

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

풀이

가로 길이만 봤을 때 1과 2의 합으로 n을 만들 수 있는 개수를 구하는 문제이다.
[프로그래머스] 멀리 뛰기 와 거의 유사한 문제이다.
1부터 계속 차례대로 나열해보면 결과값들은 피보나티 수열의 형태이다.

function solution(n) {
    let arr = [1,1];
    for(let i = 2; i <= n; i++){
        arr.push((arr[i-2] + arr[i-1]) % 1_000_000_007);
    }
    return arr[n] ;
}

회고

처음에 피보나치 수열을 모두 구하고 반환 시 1_000_000_007 로 나눴는데 시간 초과가 났다.

나누기 연산은 O(1)인 줄 알았는데 문자열의 길이가 클수록 연산시간이 더 걸린다고 한다.
그래서 arr에 push할때 해당 값을 1_000_000_007 으로 나눈 값을 넣어줬다.