문제 설명
가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.
- 타일을 가로로 배치 하는 경우
- 타일을 세로로 배치 하는 경우 예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다.
직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.
제한사항
- 가로의 길이 n은 60,000이하의 자연수 입니다.
- 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.
| 입출력 | 예 |
|---|---|
| n | result |
| 4 | 5 |
입출력 예 설명
입출력 예 #1
- 다음과 같이 5가지 방법이 있다.
풀이
- 처음에 가짓수를 구하는 패턴을 찾으려고 하나하나 경우의 수를 구하다가 가짓수 패턴이 피보나치수열과 너무 유사해서 피보나치를 적용했더니 풀렸던 문제였습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
const solution = (n) => {
// 타일링 가짓수를 담은 배열
let arr = [0,1,2]
// n의 값이 3까지는 타일링을 배치할수 있는 가짓수도 같으므로 그대로 리턴
if(n <= 3) return n
// 타일링의 가짓수는 피보나치 수열처럼 이전 값들을 더하면 됩니다,
for(let a = 3; a <= n; a++){
// arr[1] => a-2, arr[2] = a-1
// arr[1]에 이전값(a - 1)을 넣기 위해 미리 arr[0]에 arr[1]과 arr[2]를
// 더한후 1,000,000,007을 나눈값으로 변경
// ex ) a = 3, arr = [ 0, 1, 2 ]
arr[0] = (arr[1] + arr[2]) % ( 10** 9 + 7);
// arr[1]을 a-2 값으로 변경
arr[1] = arr[2];
// arr[2]를 a-1 값으로 변경
arr[2] = arr[0];
// ex ) a = 3, arr = [ 3, 2, 3 ]
}
return arr[0];
}
// 0 -> 0
// 1 = 0 + 1 -> 1
// 2 = 1 + 1 -> 2
// 3 = 1 + 2 -> 3
// 4 = 2 + 3 -> 5
// 5 = 3 + 5 -> 8
// 6 = 5 + 8 -> 13
// 7 = 8 + 13 -> 21
// 8 = 13 + 21 -> 34
// 9 = 21 + 34 -> 55
// 10 = 34 + 55 -> 89
// 11 = 55 + 89 -> 144
// 12 = 89 + 144 -> 233
// 13 = 144 + 233 -> 377