> For the complete documentation index, see [llms.txt](https://songeun.gitbook.io/coding-test/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://songeun.gitbook.io/coding-test/lv.2/3.md).

# 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];
}
```

그래서 코드를 깔끔하게 작성한 다른 사람의 코드를 보면 위와 같이 작성할 수 있다. 너무 어렵다🥲