[js문제풀이]2 x n 타일

문제

문제 설명

가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.

• 타일을 가로로 배치 하는 경우
• 타일을 세로로 배치 하는 경우

예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다.

직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

제한사항

• 가로의 길이 n은 60,000이하의 자연수 입니다.
• 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

---

입출력 예

nresult

4

5

입출력 예 설명

입출력 예 #1
다음과 같이 5가지 방법이 있다.

접근 및 풀이

n이 1인 경우부터 차례대로 타일을 만들어 가며 패턴을 구하는 방식으로 접근했다. 무슨 원리인지 잘 모르겠는데 피보나치 패턴이 보여서 피보나치를 사용했다. 다른 사람의 해설을 보니 납득이 갔다. (n-1번째 타일의 경우의 수들에서 세로방향 타일 하나를 최우측에 배치하는 경우) + (n-2번째 타일의 경우의 수들에서 세로세로, 가로가로 타일을 최우측에 배치하는 경우) = n-2번째 타일의 경우의 수들에서 세로세로 타일을 배치한 경우들이 겹치므로 그들을 지워주면 최종적으로 다음의 식이 도출된다. f(n) = f(n-1) + f(n-2) + f(n-2) - f(n-2) = f(n-1) + f(n-2)

코드

function solution(n) {
  let v1 = 0;
  let v2 = 1;
  let acc = 0;
  while(n--){
    acc = (v1 + v2) % 1000000007;
    [v1, v2] = [v2, acc];
  }
  return acc;
}

출처

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