Programmers | Level 2 | 2 x n 타일링

Programmers | Level 2 | 2 x n 타일링

Problems

• 📘 Src: Programmers
• 🗂️ Cat: Dynamic Programming

󰧭 Description

2×1 타일을 이용해 2×n 크기의 바닥을 채우는 방법의 수를 구하는 문제입니다. 타일을 가로 또는 세로로 배치할 수 있으며, 이 두 가지 방법을 조합해 주어진 크기의 바닥을 완전히 덮어야 합니다. 가로의 길이 n이 주어졌을 때, 가능한 모든 타일 배치 방법의 수를 구하고, 그 결과를 1,000,000,007로 나눈 나머지를 반환합니다.

 Constraints

• 가로의 길이 n은 60,000 이하의 자연수입니다.
• 결과가 매우 커질 수 있으므로, 정답은 1,000,000,007로 나눈 나머지를 반환해야 합니다.

󰦕 Examples

n	result
4	5

Solutions

󰘦 Code

class Solution {

    private static final Integer MOD = 1_000_000_007;

    public int solution(int n) {
        // n이 1인 경우 처리
        if (n == 1) return 1;

        // DP 배열 초기화
        int[] dp = new int[n + 1];
        dp[1] = 1;  // 길이가 1인 바닥을 채우는 방법
        dp[2] = 2;  // 길이가 2인 바닥을 채우는 방법

        // DP 점화식을 사용하여 계산
        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
        }

        // 결과 반환
        return dp[n];
    }
}

 Approach

이 문제는 Dynamic Programming(동적 계획법)을 활용하여 해결할 수 있습니다. 문제에서 주어진 조건을 고려했을 때, 단순하게 가능한 모든 타일 배치 방법을 일일이 계산하기에는 비효율적입니다. 따라서 중복되는 계산을 줄이고 효율적으로 문제를 해결하기 위해서 DP를 적용하는 것이 적합합니다.

1. 문제 분석

이 문제의 목표는 2×n 크기의 바닥을 2×1 타일로 모두 채우는 방법의 수를 구하는 것입니다. 타일은 가로로 배치하거나, 세로로 배치할 수 있습니다. 이를 통해 타일링 문제를 해결하는 과정에서 주어진 문제의 구조를 이해하고, 그에 따라 점화식을 유도할 수 있습니다.

2×n 크기의 바닥을 채우는 방법은, 마지막 타일을 어떻게 놓느냐에 따라 크게 두 가지로 나눌 수 있습니다.

• 세로 타일을 마지막에 놓는 경우
  • 이 경우, 마지막에 놓는 타일은 2×1 크기의 타일 하나가 세로로 놓입니다.
  • 따라서, 이 경우의 문제는 길이가 n - 1인 바닥을 모두 채운 후, 마지막에 세로로 2×1 타일을 하나 추가하는 문제로 환원됩니다.
  • 즉, 길이 n의 바닥을 채우는 방법의 수는 길이 n - 1인 바닥을 채우는 방법의 수와 동일합니다.
• 가로 타일을 마지막에 놓는 경우
  • 이 경우, 마지막에 놓는 타일은 2×1 크기의 타일 두 개가 가로로 나란히 놓입니다.
  • 이때, 두 칸을 가로로 채우게 되므로, 길이가 n - 2인 바닥을 모두 채운 후, 마지막에 가로로 2×1 타일 두 개를 추가하는 문제로 환원됩니다.
  • 즉, 길이 n의 바닥을 채우는 방법의 수는 길이 n - 2인 바닥을 채우는 방법의 수와 동일합니다.

이 두 가지 경우를 모두 고려했을 때, 길이 n의 바닥을 채우는 경우의 수는 길이 n - 1의 바닥을 채우는 경우의 수와 길이 n - 2의 바닥을 채우는 경우의 수를 더한 것과 같습니다. 이를 수식으로 표현하면 다음과 같은 점화식을 도출할 수 있습니다:

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

이 점화식은 길이 n의 바닥을 채우기 위한 방법이, 길이 n - 1까지 채운 후 세로로 타일 하나를 놓는 경우와, 길이 n - 2까지 채운 후 가로로 타일 두 개를 놓는 경우의 합으로 계산된다는 뜻입니다.

다음으로, 예시를 통해 이 아이디어가 어떻게 적용되는지 살펴보겠습니다.

• n이 1인 경우:
  • 이때는 바닥의 길이가 1이므로, 하나의 2×1 타일을 세로로 배치하는 방법밖에 없습니다.
  • 따라서 dp[1] = 1입니다.
• n이 2인 경우:
  • 이때는 바닥의 길이가 2이므로, 두 가지 방법이 가능합니다:
  • 세로로 2×1 타일을 두 개 배치하는 방법
  • 가로로 2×1 타일 두 개를 나란히 배치하는 방법
  • 따라서 dp[2] = 2가 됩니다.
• n이 3인 경우:
  • 이때는 바닥의 길이가 3이므로, 다음과 같은 세 가지 방법이 가능합니다:
  • 세로로 2×1 타일을 하나 배치하고, 나머지 2칸을 dp[2]로 채우는 방법 (dp[3] = dp[2])
  • 가로로 2×1 타일 두 개를 배치하고, 나머지 1칸을 dp[1]로 채우는 방법 (dp[3] = dp[1])
  • 따라서 dp[3] = dp[2] + dp[1] = 3가 됩니다.

이처럼, 점화식을 통해 작은 문제를 해결하면서 점차적으로 큰 문제를 해결할 수 있습니다. 이를 일반화하면, n 길이의 바닥을 채우는 방법은 항상 dp[n-1]과 dp[n-2]의 합으로 구할 수 있습니다.

이 문제를 DP를 활용해 해결할 수 있는 이유는 바로 문제의 중복되는 부분 구조 때문입니다. 큰 문제를 작은 문제로 나누어 해결한 결과를 사용하여 효율적으로 최종 해답을 구할 수 있습니다.

2. 초기 설정

이 문제에서 동적 계획법을 사용하기 위해서는 먼저 작은 문제들에 대한 해답을 설정해야 합니다. 이러한 초기 값들은 더 큰 문제들을 해결하는 데 필요한 기반이 됩니다.

먼저, n이 1인 경우에는 다음과 같은 특별한 처리가 필요합니다. 길이가 1인 바닥을 채우는 방법은 세로로 타일 하나를 놓는 방법밖에 없으므로, dp[1]은 1이 됩니다.

// n이 1인 경우, 타일링 방법은 1가지
if (n == 1) return 1;

작은 문제부터 차례로 해결해 나가는 DP의 특성상, 기본적인 초기 값을 정의합니다. 이 값들은 나중에 더 큰 문제들을 해결하기 위한 기초가 됩니다. 먼저, 배열의 인덱스와 바닥의 길이 n을 직관적으로 대응시키기 위해 길이 n + 1 크기의 dp 배열을 생성합니다. 이렇게 하면 배열의 인덱스 i가 길이 i인 바닥을 채우는 방법의 수를 나타내므로, 더 직관적이고 사용하기 쉽습니다.

// DP 배열 초기화
int[] dp = new int[n + 1];

이제 바닥의 길이가 1인 경우와 2인 경우에 대한 해답을 초기화합니다. 이 두 가지 경우는 가장 작은 단위의 문제들로, 이후 더 큰 문제들을 해결할 때 필요한 초기 조건 역할을 합니다. 이 값들은 점화식을 적용하여 더 큰 n에 대한 해답을 계산할 수 있도록 합니다.

dp[1] = 1;  // 길이가 1인 바닥을 채우는 방법은 세로 타일 하나뿐
dp[2] = 2;  // 길이가 2인 바닥을 채우는 방법은 세로 타일 두 개 또는 가로 타일 두 개

• dp[1] = 1: 길이가 1인 바닥을 채우는 방법은 세로 타일 하나뿐입니다.
• dp[2] = 2: 길이가 2인 바닥을 채우는 방법은 두 가지가 있습니다:
  • 세로 타일 두 개로 채우는 경우
  • 가로 타일 두 개로 채우는 경우

이렇게 초기 설정을 완료한 후, n ≥ 3인 경우는 점화식을 적용하여 순차적으로 계산해 나갈 수 있습니다.

3. 점화식을 통한 계산

주어진 n에 대해서 dp[n] 값을 계산하기 위해, dp[3]부터 dp[n]까지 점화식을 반복하여 적용합니다.

// DP 점화식을 사용하여 계산
for (int i = 3; i <= n; i++) {
    dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
}

매 연산마다 1,000,000,007로 나눈 나머지를 구해줍니다. 이는 결과가 매우 커질 수 있으므로, 계산 중간에 값이 오버플로우하지 않도록 하기 위함입니다.

4. 최종 결과 반환

계산이 완료되면 dp[n]에 해당하는 값을 반환합니다. 이 값이 곧 n 크기의 바닥을 타일로 채울 수 있는 방법의 수가 됩니다.

// 최종 결과 반환
return dp[n];

󰄉 Complexity

• ⏳ TC: O(n)
• 💾 SC: O(n)

이 알고리즘은 동적 계획법을 활용하여 DP 테이블을 한 번 순회하며 값을 계산하므로, 시간 복잡도는 O(n)입니다. 또한, 크기 n + 1의 배열을 사용하여 결과를 저장하기 때문에 공간 복잡도 역시 O(n)입니다. 이 문제는 점화식을 기반으로 동적 계획법을 적용하는 전형적인 예시로, 작은 문제를 해결한 결과를 이용해 더 큰 문제를 해결하는 방식입니다. 또한, 값이 커질 수 있는 상황을 고려해 나머지 연산을 사용하여 안정적인 결과를 반환하는 방법을 학습할 수 있습니다.