코딩 테스트 - 2 x N 타일링

개요

가로의 길이가 2이고, 세로의 길이가 1인 직사각형 모양의 타일이 있다. 이 타일들로 가로의 길이가 2이고 세로의 길이가 n인 바닥을 가득 채울 수 있는 방법의 수를 반환해야한다.

조건

• 가로의 길이 n은 60,000이하 자연수이다.
• 경우의 수가 많아질 수 있으므로 경우의 수를 1,000,000,007로 나눈 나머지를 반환해야 한다.

풀이

귀납적으로 n = 1, 2, 3, 4… 그려보다보면 규칙을 발견할 수 있다. n = 4일 때를 가정해보면, 우측에 가로 x 세로가 [1 x 2]와 [2 x 2]가 비워져 있을 때를 생각해보자. 전자는 n = 3일때, 후자는 n = 2일 때와 사실상 동일하다(다른 분기가 발생하지 않는다). 단, [2 x 2]가 비워져 있을 때에는 세로 방향으로 2개를 놓는 것은 생각하지 않는다. 이는 n = 3일 때의 경우와 동일한 상황이기 때문이다.

그보다도 1,000,000,007로 나누는 이유가 무엇일까. 우선 이렇게 특정한 수로 나눈 값을 취하는 방법을 모듈러 연산(Modular arithmaetic)이라고 한다. 암호 알고리즘에도 종종 사용한다고 한다. $mod m$이면, 항상 $0$ ~ $m$ 내의 값이 결과값이 된다.

1. 소수이다. 다른 수로 나누는 것보다 연산의 정확도가 높아진다.
2. 모듈러 결과값이 지나치게 작다면 언어의 표현력을 비효율적으로 사용하는 것이기 때문이다. init은 약 2 * e9까지 표현할 수 있다. 다만, 2e9를 기준으로 하면, 덧셈이나 뺄셈 등 연산에서 오버플로우가 발생할 수 있다. 따라서, 절반인 1e9에 가까운 수 중 1e9 + 7을 사용하는 것이다.

대부분 어떤 결과에 이 값을 나누기보다 연산과정에서 적용하는 경우가 많다고 한다. 따라서 모듈러를 연산에 적용한다면, 연산자 분배의 법칙이 무엇인지 일단 알아두자.

덧셈: (A + B) % M = ((A % M) + (B % M)) % M
곱셈: (A * B) % M = ((A % M) * (B % M)) % M
뺄셈: (A * B) % M = ((A % M) - (B % M) + M) % M

// 1. 개인풀이
function solution(n) {
    const factorial = [0, 1, 2];
    for (let i = 3; i <= n; i++) {
        arr[i] = (arr[i - 2] + arr[i - 1]) % 1000000007;
    }
    return arr[n];
}

Reference

PS기초 - 왜 1e9 + 7로 나눈 나머지를 고집할까
모듈러 연산