[백준] 11727번 2×n 타일링 2 해설 및 풀이 (Python, Java)

백준 11727번 2×n 타일링 2

https://www.acmicpc.net/problem/11727

---

문제

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

 

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

---

 

풀이 방법 도출

 

이 문제는 동적 프로그래밍(DP)로 해결할 수 있습니다.

 

문제는 2×n 크기의 직사각형을 채우는 경우의 수를 구하는 것입니다.

사용할 수 있는 타일의 경우의 수는 1×2(세로), 2×1(가로), 2×2 (정사각형)이 있습니다.

 

1. dp의 초기화는 3 이상으로 합니다. dp[1] = 1, dp[2] = 3
2. dp[1] = 1은 오른쪽에 2×1 타일 하나를 붙이는 경우입니다.
3. dp[2] = 3는 오른쪽에 1×2 두 개 또는 2×2 하나를 붙이는 경우입니다.

 

배열의 크기를 꼭 3 이상으로 해야 n이 1일 때도 작동합니다.

모든 결과는 10007로 나눈 나머지를 출력해야 합니다.

 

 

시간 복잡도

• O(N)

---

핵심 코드 삽입 및 설명

 

Python

 

처음에 작성한 코드

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 3

for i in range(3, n + 1):
    dp[i] = (dp[i - 1] + dp[i - 2] * 2) % 10007

print(dp[n])

 

최소 크기를 3으로 만들어야 하기 때문에 dp 초기화를 다시 해야 한다.

 

최종 Python 코드

import sys
input = sys.stdin.readline

n = int(input())
dp = [0] * (max(3, n + 1))  # 최소 크기 3으로 만들어야 dp[2] 접근 가능

dp[1] = 1
dp[2] = 3

for i in range(3, n + 1):
    dp[i] = (dp[i - 1] + dp[i - 2] * 2) % 10007

print(dp[n])

 

 

Java

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        int[] dp = new int[Math.max(3, n + 1)];
        
        dp[1] = 1;
        dp[2] = 3;

        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2] * 2) % 10007;
        }

        System.out.println(dp[n]);
    }
}