[프로그래머스] 3 x n 타일링, JavaScript 풀이

문제

문제링크

프로그래머스

 

 

 

 

제한사항

• 가로의 길이 n은 5,000이하의 자연수 입니다.
• 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

입출력 예시

n	결과
4	11

 

n=4 일때 타일을 모두 채우는 경우의 수.

 

문제 풀이

이런 문제의 접근은 n이 1일때부터 차근차근 접근해야한다.

하지만 세로가 3으로 고정되어 있으므로 n이 홀수일 때, 타일을 모두 채우는 경우의 수는 0이다.

따라서 우리는 짝수 내용만 고려하면 된다.

 

그럼 n=2 일 때는 3개로 주어진 예시에서 찾을 수 있다.

n=2일때 타일을 모두 채우는경우의 수

 

n=4일 때는 11개로 설명에 나와있다.

여기서 주의 깊게 봐야할 점은 n=4일 때, n=2일 때와 비교해서 다른 점은 가로로 타일이 2개씩 들어가는 형태를 구성할 수 있다는 점이다.

n=6일 때를 세어보자.

n=6일 때 타일을 모두 채우는 경우의 수

가로를 2/2/2로 나누어 채우는 방식(3*3*3)

(1, 2, 4, 5, 9, 10, 12, 13, 14, 15, 17, 18, 21, 22, 23, 24, 25, 26, 31, 32, 34, 35, 36, 37, 39, 40, 41)

 

+ 가로를 4/2로 나누어 채우는 방식(2*3*2)

(3, 7, 8, 11, 16, 19, 20, 28, 29, 30, 33, 38) 

 

+ 가로를 6개 통채로 채우는 방식(2)

(6, 27)

 

총 41개 구성되어 있다.

 

n=8일 때는

가로를 2/2/2/2로 나누어 채우는 방식(3*3*3*3)

+ 가로를 2/2/4로  형태로 나누어 채우는 방식(2* 3*3*3)

+ 가로를 4/4로 형태로 나누어 채우는 방식(2*2)

+ 가로를 2/6로 형태로 나누어 채우는 방식 (3* 2* 2)

+ 가로를 8개 통채로 채우는 방식 (2)

8개 통채로 채우는 방식

로 총 153개로 구성되어있다.

 

이로써 2일때, 4일때, 6일때, 8일때를 보면 각각 3, 11, 41, 153으로 여기서 점화식을 찾아 메모이제이션을 이용하여 구현해야한다.

 

각 연관 관계를 보면 (n=6) = 4 * (n=4) - (n=2)라는 관계식을 찾을 수 있고, 이를 n=8 에 대입해보면,

(n=8) = 4 * (n=6) - (n-4) = 4 * 41 - 11 = 153 으로 성립하는 것을 볼 수 있다.

 

이를 이용해 코드를 구성하면 다음과 같이 DP 배열을 만들 수 있다.

( n>>1은 shift 연산자로 n/2의 소수점 자리를 버린 것과 같은 값이 나온다.)

const dp = Array((n >> 1)+1).fill(0);
dp[0] = 1;
dp[1] = 3;
dp[2] = 11;

for (let i = 3; i <= (n>>1); i++) {
    dp[i] = (4 * dp[i-1] - dp[i-2]);
}

 

여기서 조심해야하는 점은 제한사항을 잊지 않고 적용 하는 것이다.

제한사항
- 가로의 길이 n은 5,000이하의 자연수 입니다.
- 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

 

제한사항 중, 경우의 수를 1,000,000,007으로 나눈 나머지를 반환하기에 마지막에만 적용하면 될 것 같지만

숫자가 커지는 경우, 연산 자체로 인해 시간초과가 날 수 있기에 DP 배열에 저장할 때부터 나누어야한다.

단, 중간에 나머지 값보다 n+1 값이 큰 경우 음수 값이 나올 경우가 있으므로 해당 경우만 예외처리를 해야한다.

 

이 내용을 반영하여 코드를 작성하면 다음과 같다.

Code

const DEVIDED = 1000000007;

function solution(n) {
    if (n & 1) return 0;
    const dp = Array((n >> 1)+1).fill(0);
    dp[1] = 3;
    dp[2] = 11;
    
    for (let i = 3; i <= (n>>1); i++) {
        dp[i] = (4 * dp[i-1] - dp[i-2]) % DEVIDED;
        if (dp[i] < 0) dp[i] += DEVIDED;
    }
    
    return dp[n>>1];
}

 

 

대표적인 DP 문제이지만 나머지 값으로 예외처리를 해야한다는 것을 생각하지 못하면 틀릴 수 밖에 없는 문제이다.

간단하게 끝날 줄 알았는데 나머지 예외처리에서 시간을 많이 잡아먹어 이를 생각할 수 있도록 하는 좋은 문제라고 생각한다.