[프로그래머스] Level2 - 2 x n 타일링(Javascript)

프로그래머스

▶ 문제 요약

1. 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있다. 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 한다.

2. 타일을 채울 때 두 가지 방법 존재 가로 배치, 세로 배치

3. 경우의 수가 많아질 수 있으므로, 경우의 수를 1000000007으로 나눈 나머지를 return 해라

 

▶ 코드

function solution(n) {
    // dp테이블 생성
    let dp = [1, 2];
    const mod = 1000000007;
    for (let i = 2; i <= n; i++) {
    	dp[i] = (dp[i-1] + dp[i-2]) % mod;
    }
    return dp[n-1];

}

▶ 풀이 과정

1. 다이나믹 프로그래밍을 활용한 문제이다. 그림을 보면 조금 이해하는데 도움이 될 것이다.

위의 그림을 보면 세로 길이 2, 가로의 길이가 n = 1일 때 가로 길이 2이고 세로의 길이 1인 타일을 세로로 배치해서 채울 수 있다. n = 2일 때 가로, 세로 방향을 활용해서 타일을 2가지 방법으로 채울 수 있고, n = 3이면 3가지 방법, n = 4이면 5가지 방법이 있다.

 

2. 위의 방법으로 점화식을 세울 수 있다. dp[n] = dp[n-1] + dp[n-2]이라는 식이 성립된다. 처음에 n = 1은 1, n = 2는 2라는 값을 배열에 담는다. 그리고 2부터 돌면서 위의 점화식으로 구한 값에 제한사항에 언급한 대로 1000000007를 나눈다. 

 

3. dp[n-1]을 한 이유는 dp[0]을 배열에 안 넣었기 때문에 dp[1]에 해당하는 값인 1이 dp[0]으로 인식된다. 그렇기 때문에 -1을 해줘야 우리가 원하는 값을 도출할 수 있다.

 

▶ 배운점

1. 일정한 패턴을 구해야하는 문제에 dp를 적극적으로 활용해보자. 그리고 dp문제는 직접 써보거나 그리면 도움이 된다.