[프로그래머스] 2 x N 타일링 (JS) (+모듈러 연산 방식)

직사각형 타일 채우기

 

1. 문제 설명

 

가로 길이가 2, 세로 길이가 1인 직사각형 모양의 타일이 있다.

이 타일을 이용하여 세로 길이가 2이고 가로 길이가 n인 바닥을 채우는 방법을 구하는 문제이다.

 

타일을 채우는 방법은 다음 두 가지가 있다:

1. 타일을 가로로 배치하는 경우
2. 타일을 세로로 배치하는 경우

그래서 가로 길이 n = 7인 직사각형은 아래처럼 타일로 채울 수 있다. 

 

---

2. 해결 과정

이 문제는 동적 프로그래밍(DP)을 사용하여 풀 수 있다.

DP는 작은 문제부터 차근차근 해결하여 큰 문제를 푸는 방식이다.

 

a.  기본 아이디어

가로 길이 n인 직사각형 바닥을 채우는 방법을 생각해 보면:

• 마지막에 가로로 타일 1개를 놓은 경우, 남은 바닥의 길이는 n-1이 된다. (경우 1) 
• 마지막에 세로로 타일 2개를 놓은 경우, 남은 바닥의 길이는 n-2가 됩니다. (경우 2) 

따라서 dp[i] (가로 길이가 i인 바닥을 채우는 방법의 수)는 다음과 같은 점화식을 가질 수 있다. 

dp[i] = dp[i-1] + dp[i-2]

 

이때 경우의 수가 매우 커질 수 있기 때문에 모듈러 연산을 사용하여 결과를 1,000,000,007로 나눈 나머지를 계산해야 했다.

 

b. 모듈러 연산과 1000000007의 사용 이유

여기서 중요한 부분이 바로 모듈러 연산이다.

 

문제에서 경우의 수가 커질 수 있기 때문에 1,000,000,007로 나눈 나머지를 구하라고 했다. 왜 하필 이 숫자일까요?

 

모듈러 연산은 큰 수의 오버플로우를 방지하기 위한 수학적 도구입다.

1,000,000,007은 큰 소수이면서도, 컴퓨터가 다룰 수 있는 범위 안에서 오버플로우 없이 큰 수를 처리할 수 있도록 도와준다고 한다.

소수를 사용하는 이유는 계산에서 충돌이나 잘못된 값이 나오는 문제를 줄이기 위해서입니다. 소수는 나눗셈 연산이 필요할 때 매우 유리하며, 계산의 성능을 보장한다고 한다. 

---

 

3. 코드 구현

다음은 이를 바탕으로 한 동적 프로그래밍 구현 코드입니다.

function solution(n) {
    const dp = [0, 1, 2];  // dp 배열 초기화 (dp[1] = 1, dp[2] = 2)
    
    for (let i = 3; i <= n; i++) {
        // 타일 가로 배치 한 경우 (dp[i-1]) + 타일 세로 배치한 경우 (dp[i-2])
        dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;
    }
    
    return dp[n];  // n번째 값 반환
}

 

---

4. 동작 설명

1. dp[1]은 타일 1개를 세로로 배치한 경우 1가지 경우의 수를 의미합니다.
2. dp[2]는 타일을 2개 세로로 배치하거나, 가로로 배치한 경우로, 2가지 경우의 수가 있습니다.
3. dp[i]는 dp[i-1]과 dp[i-2]를 더한 값인데, 그 이유는 가로 2칸의 타일을 채우는 마지막 경우는 가로로 1칸을 추가하거나, 세로로 2칸을 추가하는 두 가지 경우이기 때문입니다.
4. 결과적으로 dp[n]을 반환하면, n 길이의 바닥을 채우는 방법의 수를 구할 수 있습니다.

이 알고리즘은 O(n)의 시간 복잡도를 가지게 된다. 

---

5. 결론

이 문제를 해결하기 위해서는 동적 프로그래밍의 원리를 이해하고, 모듈러 연산의 중요성을 파악해야 했습니당.