백준 11726 - 2 x n 타일링 : dynamic programming

문제

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

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

 

다이나믹 프로그래밍 방법

---

기본적인 다이나믹 프로그래밍 방법은 계산을 용이하게 하는데에 있다. 

즉, 일반적인 완전탐색처럼 모든 계산을 다 하되, 다이나믹 프로그래밍의 간단한 개념은 주어지는 모든 계산을 하지 않고, 필요한 계산이 있으면 재사용하는 것이다.

 

간단히 예를들어, 피보나치수열처럼 같은 계산 구조가 반복될 경우, 새로운 해를 구할 때마다 모든 계산을 반복하지 않고 1번 계산했던것을 재사용한다면 계산량을 엄청나게 줄일 수 가 있다.

 

 

풀이 (1)

---

직사각형을 채우는방법은 2가지 밖에 없다. 1x2 타일을 1개 두거나 2x1 타일을 위아래로 2개 두는 방법이다.

그러므로 2가지 방법을 계속 나누어서 진행하면 답을 구할 수 가 있다.

이 때, 한 번 계산한 결과를 저장해두어서 다음번에 필요할경우 재사용할 수 있도록 한다.

 

2xn 타일을 채우는 가짓수를 f(n) 이라 하면 f(n) = f(n-1) + f(n-2) 가 된다. // 바로 위에서 한 말을 식으로 옮겼다.

위의 사진 처럼 f(6)을 구하는 경우 f(3)은 3번 계산이 되는데, f(3)을 계산하려면 f(2)와 f(1)을 계산해야하고, f(2)를 계산하려면 f(1)과 f(0)을 계산해야한다. 그러므로 처음 f(3)은 계산하고, 이 결과를 저장해두려는 계획이다.

 

(이 문제를 풀 때 위 사진에서 f(0)은 필요없다.)

import sys
from collections import defaultdict
input = sys.stdin.readline

limit_number = 15000
sys.setrecursionlimit(limit_number)

dic = defaultdict(int)
n = int(input())

def ccc(n,res):
    if n == 0 :
        res += 1
        return 1
    elif n < 0 : 
        return 0
    
    if dic[n] != 0:
        return dic[n]
    
    for i in [1,2]:
        res += ccc(n-i,res)
        dic[n] = res
    
    return res

ccc(n,0)
print(dic[n]%10007)

 

 

풀이 (2)

---

풀이 1은 주어진 수에따라 모든 계산을 하며 계산 결과를 메모이제이션(memoization) 하는 다이나믹 프로그래밍 방법의 하나였다.

두번째 방법은, 하나의 배열을 사용하여 이전의 결과로 정답을 구하는 다이나믹 프로그래밍 방법이다.

배열 result 를 정의하고 result[i] = 2 x i 타일링 경우의 수 라고 하자.

 

아까 1번에서 구한 점화식 f(n) = f(n-1) + f(n-2) 을 사용하여 하나의 배열 속에서 계산이 가능하다.

import sys
input = sys.stdin.readline

n = int(input())

result = [0 for _ in range(n+1)]

if n < 3:
    print(n)
else : 
	result[1] = 1
	result[2] = 2
	for i in range(3, n+1):
		result[i] = result[i-1] + result[i-2]

	print(result[n]%10007)

 

풀이 (3)

---

이제 이 문제가 피보나치수열과 같은 구조임을 알게되었다.

식 : f(n) = f(n-1) + f(n-2)

초기 조건 : f(1) = 1, f(2) = 2

 

그러므로 피보나치문제를 푸는 것처럼 풀 수 있다. 위의 방식말고도 간단한 방법이 존재한다.

# 피보나치
# 0 1 1 2 3 5 8 13 21 34 
import sys
input = sys.stdin.readline

n = int(input())
if n < 3:
    print(n)
else:
    a, b = 1, 2
    while(n > 1):
        a, b = b, a+b
        n -= 1
    print(a%10007)

반복문을 도는 방법이나 a 와 b 중 무엇을 출력하는가는 조건을 어떻게 주느냐에따라 달라질 수 있다.

 

하지만 1,2,3 번 풀이 무엇을 선택하든 파이썬이라그런지 백준 채점속도가 매우 느리다.