Lv3. 2 x n 타일링

문제 설명

자료 구조

  • arr
    • 타입 : 배열
    • 저장 데이터 : 피보나치 수열을 만들기 위한 변수
  • i
    • 타입 : 정수
    • 저장 데이터 : arr 배열에 사용할 인덱스

풀이 과정

가로가 n인 바닥을 채우는 경우의 수 := f(n)

예) f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 5 ...

f(3) = f(1)에서 두 칸을 채우는 방법 + f(2)에서 한 칸을 채우는 방법
f(4) = f(2)에서 두 칸을 채우는 방법 + f(3)에서 한 칸을 채우는 방법
f(5) = f(3)에서 두 칸을 채우는 방법 + f(4)에서 한 칸을 채우는 방법...

∴ f(n) = f(n-2) + f(n-1)

구현 (JavaScript)

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

출처: 프로그래머스

좋은 웹페이지 즐겨찾기