(BOJ)-11726, Python

문제 요약

출처: (BOJ)11726 - 2×n 타일링

$2×n$ 크기의 직사각형을 $1×2, 2×1$ 타일로 채우는 경우의 수를 구하는 문제이다.

• 경우의 수를 10,007로 나눈 나머지를 출력한다.

접근 과정

1. 완전탐색 접근(재귀)

$1\times2$ 타일을 선택하는 경우와 $2\times1$ 타일을 선택하는 경우로 나누기 위해 재귀를 활용하여 접근하기로 했다. 결과는 시간초과였다.

코드 구현

N = int(input())

def recursion(idx):
    global count
    if idx >= N+1:
        return 
    if idx == N:
        count += 1
        return 

    #1X2 타일을 선택하는 경우
    recursion(idx + 2) 
    #2X1 타일을 선택하는 경우
    recursion(idx + 1)

count = 0
recursion(0)
print(count%10_007)

2. DP 접근(메모이제이션)

위 재귀 완전탐색 방식의 중복 계산 문제를 개선시키기 위해 DP(메모이제이션) 로 접근하였다. 결과는 맞았습니다!

코드 구현

N = int(input())
dp = [-1 for _ in range(N)]

def recursion(idx):
    if idx >= N+1:
        return 0 
    if idx == N:
        return 1
    if dp[idx] != -1:
        return dp[idx]
    
    #1x2를 넣는 경우와 2X1를 넣는 경우
    dp[idx] = recursion(idx + 2) + recursion(idx + 1)
    
    return dp[idx]

recursion(0)
print(max(dp)%10_007)

3. DP 접근(점화식)

또 다른 해결 방법으로, 점화식을 활용하여 문제를 해결할 수 있다. 즉, 규칙을 발견하면 쉽게 문제를 풀 수 있다는 의미이다. 이 문제 역시 점화식을 유도할 수 있는데, $n$이 $1$부터 $5$까지일 때를 살펴보도록 하자:

• $a_1 = 1$
• $a_2 = 2$
• $a_3 = 3$
• $a_4 = 5$
• $a_5 = 8$

값이 피보나치 수열처럼 전개되는 것을 확인할 수 있다. 따라서, $a_n = a_{n-1} + a_{n-2}$ 라는 점화식을 얻을 수 있다.

이를 다른 관점에서 생각해보면, 마지막에 $1\times2$ 타일로 채워졌거나 $2\times1$ 타일로 채워졌을 두 가지 경우로 나눌 수 있다.

• $1\times2$ 타일로 채운 경우: 남은 공간이 $n-2$ 크기가 되므로, $a_{n-2}$의 경우의 수가 된다.
• $2\times1$ 타일로 채운 경우: 남은 공간이 $n-1$ 크기가 되므로, $a_{n-1}$의 경우의 수가 된다.

결국, 두 가지 경우를 더한 값이 최종 경우의 수가 된다는 것이다!

사실, 이미 2번 접근을 통해 이 점화식과 같은 논리를 도출했다는 것을 알 수 있다!

코드 구현

N = int(input())

dp = [0 for _ in range(N+1)]
for idx in range(1, N+1):
    if idx < 3:
        dp[idx] = idx
    else:   
        dp[idx] = dp[idx-1] + dp[idx-2]
    
print(dp[N]%10007)

회고

이번 문제의 점화식을 이미 알고 있었기에, 쉽게 접근하고 해결할 수 있었다.