[코플릿]tiling

코드스테이츠 과제 코드를 공부 목적으로 변형 해서 정리 하였습니다.

✅문제

세로 길이 2, 가로 길이 n인 2 x n 보드가 있습니다. 2 x 1 크기의 타일을 가지고 이 보드를 채우는 모든 경우의 수를 리턴해야 합니다.

 

⛔주의

• 타일을 가로, 세로 어느 방향으로 놓아도 상관없습니다. (입출력 예시 참고)

 

💬입출력 예시

let output = tiling(2);
console.log(output); // --> 2

output = tiling(4);
console.log(output); // --> 5
/* 
2 x 4 보드에 타일을 놓는 방법은 5가지
각 타일을 a, b, c, d로 구분

2 | a b c d
1 | a b c d 
------------

2 | a a c c
1 | b b d d 
------------

2 | a b c c
1 | a b d d 
------------

2 | a a c d
1 | b b c d 
------------

2 | a b b d
1 | a c c d 
------------
*/

🍀해결코드

function factorial(n) {
    let result = 1;
    for (let i = 2; i <= n; i++) result *= i;
    return result;
}

function count(n, k) {
    let result = factorial(n + k) / (factorial(k) * factorial(n))
    return result
}

let tiling = function (n) {
    // TODO: 여기에 코드를 작성합니다.
    let temp = 0;
    let result = 0
    if (n === 0) {
        return 0
    }
    for (let i = n; i >= 0; i -= 2) {
        console.log(i, temp)
        result += count(i, temp)
        temp += 1;
    }
    return result
};

---

🦦해설

가로타일을 하나 배치하면 그 아래는 무조건 하나의 가로타일을 배치해야 모든 공간을 채울수 있다.

 

2x2크기의 바닥이 있는 경우 세로타일 두개를 배치하는 경우와 가로타일을 두개 배치하는 경우가 있다.

2x3크기의 바닥인 경우 세로타일을 세개 배치하거나 세로타일 하나 가로타일 두개를 배치하는 경우가 있다.

세로타일을 1이라 하고, 가로타일 두개를 0이라고 하면 경우의수는 다음과 같다

111,10,01

2x4인경우는 1111,110,101,011,00이다.

쉽게 [1,1,1,1] 중 나올수있는 경우의 수 + [1,1,0]중 나올수있는 경우의 수 + [0,0] 중 나올수있는 경우의 수 이다.

 

중복된 숫자 사이에서 경우의수를 얻는 공식은 다음과 같다.

1110000처럼 1이 3개, 0이 4개인 상황에서 나올수있는 모든 경우의 수는 ( 4+3 )! / ( 4! * 3! )

 

팩토리얼을 factorial함수로 만들었다.

 

위에서 말한 중복된 숫자중 나올수 있는 경우의 수를 구하는 함수를 count에 구현했다.

 

for문을 돌면서 1이 되는 n을 2씩 감소, 0이 되는 temp을 1씩 증가시켜서 각각을 count에 보내서 나온 결과를 result에 더했다.