[python3] 백준 11726번 - 2×n 타일링

문제

2 x 1, 1 x 2 타일로 2 x n 짜리 타일을 채우는 방법의 수를 물어보고 있다.

 

이 문제를 푸는 핵심은 우리가 이전에 구했던 경우의 수 들로 다음 경우의 수를 구해야 하는 것이다. 전 항과 우리가 구하려고 하는 항의 관계를 흔히 점화식이라고 부른다.
다이나믹 프로그래밍 문제를 푸는 데의 핵심은 점화식을 구하는 것에 있다.

 

n=1 부터 초반 몇 개 항을 적다 보면, 항들 간의 관계를 생각해볼 수 있는데, 우리가 2 x k 짜리 타일을 채우는 방법을 고민할때, 2 x k 타일을 채우는 경우의 수는 2가지밖에 없다. 2 x (k-1) 짜리 타일에 1 x 2 타일을 마지막에 붙이거나, 2 x (k-2) 짜리 타일에 2 x 1 타일 2개를 2 x 2로 만들어서 붙이는 것이다. 결국 2 x n 짜리 타일을 구하는 경우의 수는 2 x (n-1) 경우의 수 + 2 x (n-2) 경우의 수라고 할 수 있다.

풀이

n = int(input())

dp =[0] * 1001
dp[1:3] = [1,2]

for i in range(3,1001):
    dp[i] = dp[i-1] + dp[i-2]

print(dp[n]%10007)

점화식을 구했으니, 초반 2개 항만 메모이제이션을 위한 dp리스트에 넣어주고, 뒤쪽 항을 차근 차근 구해주면 되겠다.

처음 나의 풀이 (비효율적)

def combi(n,k):
    if l[n][k] != 0:
        return l[n][k]
    if n==k or k==0:
        return 1
    t = combi(n-1, k) + combi(n-1, k-1)
    l[n][k] = t
    return t

n = int(input())
l = [[0 for _ in range(n+1)] for _ in range(n+1)]
ret = 0

for i in range(n//2+1):
    ret += combi(n-i, i)

print(ret%10007)

나는 dp를 한답시고 combination에 대한 table을 만들어서 문제를 풀었었는데,

위와 같이 매우 비효율적이었다,,

 

처음 손으로 써보면서 규칙성을 찾을 때 dp의 문제 풀이 방향에 맞게 작은 문제들로 더 큰 그 다음 문제를 해결할 수 있게  조금 더 깔끔하고, 명확한 규칙을 찾을 수 있게 노력해야겠다.