프로그래머스 JS [2 x n 타일링] 피보나치 수열

2 x n 타일링

문제 설명

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

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

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

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

제한사항

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

---

입출력 예nresult

4

5

---

문제의 조건에 따라 수열이 만들어지는지 하나씩 직접 만들어 살펴봅니다. // n // 1 1 // 2 2 // 3 3 // 4 5 // 5 8 // 피보나치 수열을 이루는게 보입니다. 1 + 2 = 3 2 + 3 = 5 3 + 5 = 8 ... 재귀로 작성을 하게 되면 매우매우매우 연산이 많아집니다. (원래 재귀로 작성하지 않지만) 불과 n=5를 구하기 위해서는 5번째의 피보나치 수를 구하기 위해 4번째 3번째의 피보나치 수를 구해야 하고 5번째 내부 4번째의 피보나치 수를 구하기 위해 3번째 2번째의 피보나치 수를 구해야 하고 3번째 피보나치 수를 구하기 위해 2번째 1번째의 피보나치 수를 구해야 한다. 5번째 내부 3번째의 피보나치 수를 구하기 위해 3번째 2번째의 피보나치 수를 구해야 하고 3번째 피보나치 수를 구하기 위해 2번째 1번째의 피보나치 수를 구해야 한다. [출처] 자바스크립트로 알고리즘 정리하기 #9 다이나믹 프로그래밍 개념

function solution(n) {     let [f0, f1, f2] = [1, 2, 3];     let count = 2;     while (count < n) {         if (n === 1 || n === 2) {             return n;         }         f2 = f0 + f1;         f0 = f1;         f1 = f2 % 1_000_000_007;         count++;     }     return f2 % 1_000_000_007; } solution(30);