[Python] 백준 11726번: 2xn 타일링 풀이

 

소스코드

n = int(input())
dp = [0,1,2]
for i in range(3,n+1):
    dp.append(dp[i-2] + dp[i-1])
print(dp[n] % 10007)

 

처음에는 감을 못 잡았는데 n의 갯수를 1부터 5까지 늘려가면서 규칙을 파악했다.

n=1 -> 1

n=2 -> 2

n=3 -> 3

n=4 -> 5

n=5 -> 8

 

즉, 피보나치와 같은 관계식을 이끌어 낼 수 있다.

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

 

어거지로 규칙을 알아냈긴 했는데, 왜 이렇게 되는지 생각을 해보자.

1) 2*(n-1) 에서 2xn 개로 늘리려면, 2x1 개의 타일밖에 사용하지 못한다.

-> 언제나 저 방법밖에 존재하지 않으므로 이 경우에는 dp[n-1] 의 방법 개수와 같다.

 즉, 검정색으로 색칠한 dp[n-1] 의 여러가지 방법 수에다가 빨간부분은 항상 고정인 것이다.

 

2) 2*(n-2) 에서 2xn 개로 늘리려면, 1x2 의 타일을 세로로 두개 배치하는 방법밖에 사용하지 못한다.

 

-> 검정색으로 색칠한 dp[n-2] 의 여러가지 방법 수에다가 빨간 부분은 항상 고정인 것이다.

중복되므로 X

 

-> 이렇게 되면 위에서의 dp[n-1] 에 중복되기 때문에 될 수 없다. 

 

따라서 dp[n] = dp[n-2] + dp[n-1] 이 명확해졌다.

 

소스코드는 매우 직관적으로 짜서 어렵지 않다.

dp 리스트에 n의 갯수에 따라 방법을 각 갯수 인덱스에 저장해두는 방식이다.