# 2 x n 타일링 ## **문제 설명** 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다. * 타일을 가로로 배치 하는 경우 * 타일을 세로로 배치 하는 경우 예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다. ![Imgur](https://i.imgur.com/29ANX0f.png) 직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요. **제한사항** * 가로의 길이 n은 60,000이하의 자연수 입니다. * 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요. *** **입출력 예** | n | result | | - | ------ | | 4 | 5 | **입출력 예 설명** 입출력 예 #1\ 다음과 같이 5가지 방법이 있다. ![Imgur](https://i.imgur.com/keiKrD3.png) ![Imgur](https://i.imgur.com/O9GdTE0.png) ![Imgur](https://i.imgur.com/IZBmc6M.png) ![Imgur](https://i.imgur.com/29LWVzK.png) ![Imgur](https://i.imgur.com/z64JbNf.png) ## 코드 [참고](https://velog.io/@longroadhome/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-LV.3-2-x-n-%ED%83%80%EC%9D%BC%EB%A7%81-JS) 타일을 까는 바닥은 가로 길이 n, 세로 길이 2 이다. `n = 1` 인 경우는 타일의 길이 1인 면이 오는 경우의 수 단 **한가지**이다. `n = 2` 인 경우는 (1) 세로로 타일을 2개 연달아 배치 하거나, (2) 가로로 타일을 눕혀서 배치하는 경우 **2가지**이다. `n = 3` 인 경우는 (1) 세로로 타일을 3개 연달아 배치하거나, (2) 가로로 1개 배치 + 세로로 1개 배치, (3) 세로로 1개 + 가로로 1개 배치하는 경우의 수로 **3가지**의 경우의 수가 존재한다. `n = 4` 인 경우는 (1) 세로로 4개 연달아 배치하는 방법, (2) 가로로 1개, 세로로 2개 배치, (3) 가로로 2개, (4) 세로로 2개 배 + 가로로 1개 배치, (5) 세로 1개, 가로 1개, 세로 1개 배치하는 **5가지**의 경우의 수가 존재한다. `n = 5` 인 경우는 마찬가지로 계산하면 총 8가지의 경우의 수가 나온다. `n` 의 값이 `1, 2, 3, 4, 5,...` 로 증가함에 따라 그 결과값이 `1, 2, 3, 5, 8...` 처럼 변화하고 있다. 여기에서 반환되는 결과가 바로 **피보나치 수열**임을 알 수 있다. **피보나치 수**는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 **`F(n) = F(n-1) + F(n-2)`** 가 적용되는 수 이다. 따라서 다음과 같이 점화식을 구할 수 있다. ```javascript DP[n]= DP[n-2] + DP[n-1] ``` 이 문제가 DP로 접근할 수 있는 또 다른 팁이 있다면, 문제 조건을 보면 최종 결과를 1,000,000,007로 나눈 나머지 값을 리턴해달라고 요구하고 있다. 이는 결과값이 매우 커질 수 있음을 의미하고 보통 이런 문제는 DP 와 같은 이전 값을 활용하여 누적하는 방식의 문제인 경우가 많다. ```javascript function solution(n) { return fibonacci(n); } const fibonacci = (n) => { const dp = new Array(n+1).fill(0); dp[0] = 1; dp[1] = 1; for(let i = 2; i <= n; i++) { dp[i] = (dp[i-2] + dp[i-1]) % 1000000007; } return dp[n]; } ``` 보통 피보나치를 DP로 구할 때 편의를 위해 1번째 값은 1, 2번째 값은 2로 미리 초기화하여 구현하곤 한다고 한다. ```javascript function solution(n) { let answer = [0,1] // F(0)=0, F(1)=1 // 피보나치 F(n) = F(n-1) + F(n-2) % 1000000007 for(let i=2; i <= n+1; i++) { answer[i] = (answer[i-1] + answer[i-2]) % 1000000007; } return answer.pop(); } ``` 이렇게 구현했을 때는 테스트 케이스는 일치하지만, 효율성 테스트 4번에서 시간 초과가 난다. ```javascript function solution(n) { // 피보나치 F(n) = F(n-1) + F(n-2) % 1000000007 let answer = new Array(n+1) // 배열 미리 생성 answer[0] = 0; answer[1] = 1; for(let i=2; i <= n+1; i++) { answer[i] = (answer[i-1] + answer[i-2]) % 1000000007; } return answer.pop(); } ``` 그래서 배열을 미리 생성하고 할당하는 방식을 했더니 효율성 테스트 4번은 통과했으나 이번엔 3번에서 시간 초과가 났다. ```javascript function solution(n) { // 피보나치 F(n) = F(n-1) + F(n-2) % 1000000007 let answer = new Array(n+1).fill(0); // 배열 생성 & 채워주기 answer[0] = 0; answer[1] = 1; for(let i=2; i <= n+1; i++) { answer[i] = (answer[i-1] + answer[i-2]) % 1000000007; } return answer.pop(); } ``` 그래서 다시 배열을 생성하고 채워준 형태로 할당해주었더니 통과되었다..! ### 다른 풀이 ```javascript function solution(n) { const arr = [0, 1, 2]; for (let i = 3; i <= n; i++) { arr[i] = (arr[i - 2] + arr[i - 1]) % 1000000007; } return arr[n]; } ``` 그래서 코드를 깔끔하게 작성한 다른 사람의 코드를 보면 위와 같이 작성할 수 있다. 너무 어렵다🥲 --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://songeun.gitbook.io/coding-test/lv.2/3.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.