[Javascript] 2 * n 타일링 (12900)

문제링크

코딩테스트 연습 - 2 x n 타일링

접근 방법

처음엔 n이 홀수인 경우, 짝수인 경우를 나눠서
순열 방식으로 접근하였다.

가로의 길이가 8인 타일은 8P8 + 7P6 + 6P4 + 5P2 + 4P0이고
가로의 길이가 7인 타일은 7P7 + 6P5 + 5P3 + 4P1이기 때문에

하지만 n의 너무 범위가 넓고 효율성이 낮은 factorial을 사용해서 통과를 하지 못하였다. (낮은 수에서는 제대로 타일의 수를 찾긴 하였다.)

그래서 다시 문제를 살펴보니
1일때 1P1 = 1
2일때 2P2 + 1P0 = 2
3일때 3P3 + 2P1 = 3
4일때 4P4 + 3P2 + 2P0 = 5
5일때 5P5 + 4P3 + 3P1 = 8

[n] = [n-1] + [n-2] 라는 특징을 갖고 있었다.

그래서 dp 방식으로 접근하였다.

주의점

n이 60000까지의 큰 범위를 갖는다. 
때문에 문제의 조건에서도 도출값 answer에 1000000007을 나눈 나머지 값을 구하라 하였는데,
최종적인 값 answer에 1000000007을 %하면 답을 구할 수 없다.

for(let i = 2; i < n; i++){
    dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;
}

 

이처럼 중간에 for문에서 처리해 줘야 한다.

 

// dp 코드

function solution(n) {
    var answer = 0;
    let dp = new Array(n).fill(0);
    dp[0] = 1;
    dp[1] = 2;
    
    for(let i = 2; i < n; i++){
        dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;
    }
    answer = dp[n-1]
    return answer;
}

 

// 순열을 사용한 풀이
function solution(n) {
    var answer = 0;
    if(n % 2 === 0){
        for(let oneLenTile = n, totalTile = n; oneLenTile >= 0; oneLenTile -= 2, totalTile--){
            answer += permutation(totalTile, oneLenTile)
        }
    }else{
        for(let oneLenTile = n, totalTile = n; oneLenTile > 0; oneLenTile -= 2, totalTile--){
            answer += permutation(totalTile, oneLenTile)
        }
    }
    return answer % 1000000007;
}

const factorial = (num) => {
    if(num === 0) return 1;
    
    return num * factorial(num - 1)
}

const permutation = (num1, num2) => {
    return factorial(num1) / (factorial(num2) * factorial(num1 - num2))
}