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

📝 [Lv2 2 x n 타일링]

입력

n

제한

0 < n <= 60,000
1,000,000,007으로 나눈 나머지를 return

출력

2 x n 의 직사각형을 채울 수 있는 모든 경우의 수

풀이

function solution(n){
  const list = Array.from({length: n+1})
  list[0] = 0;
  list[1] = 1;
  list[2] = 2;
  
  for(let i = 3; i <= 3 + n; i++){
    list[i] = (list[i-1] + list[i-2]) % 1000000007
  }
  
  return list[n]
}

설명

1. n = 5일때까지의 경우의 수를 전부 구해본 결과

n	n 표현식	갯수
1	ll	1개
2	ll,=	2개
3	lll, l=,=l	3개
4	llll,ll=,l=l,=ll,==	5개
5	lllll,lll=,ll=l,l=ll, =ll, l==,=l=,==l	8개

n > 3일 경우, f(n) = f(n - 1) + f(n -2) 이라는 점화식을 찾아볼 수 있었다.