[백준알고리즘] 11727번: 2xN 타일링 2 -Python

[백준알고리즘] 11727번: 2xN 타일링 2 -Python

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

11727번: 2×n 타일링 2

이전과 똑같이 두가지 방법으로 풀었다. 이전 문제인 11726번 문제 풀이와 거의 같다.

아무튼 이전 글을 거의 복사해서 써야겠다. ㅎㅎ

이번 문제에서는 첫 번째 방법의 설명이 조금 난해한 것 같아 두 번째 방법을 보고 첫 번째 방법을 봐도 괜찮을 것 같고.. 그렇다... 두 번째 방법을 보면 첫 번째 방법을 안 볼 것 같지만 말이다.

첫 번째 방법.

우선 첫 번째 방법은 Combination을 사용했다. N을 1부터 늘려가며 생각해보았다. 여기서 조합을 적용한 방법은 세로는 신경 쓰지 않고 수평선에서 길이 N을 1과 2로 채울 조합을 생각했다. 단, 이전 문제와 다른 점이 있다면, 2를 채울 때에는 두가지 방법이 있기 때문에 2를 채울때마다 2를 곱해주어야 한다. 즉, 두 칸을 차지할 때는 수평선 상으로는 한 가지 경우 같지만 실제로는 서로 다른 두 가지 경우가 존재한다는 것이다. 그렇기 때문에 두 칸을 차지할 때마다 2를 곱해주게 되고, 다른 말로 하면 두 칸의 개수의 승만큼의 2를 곱해주게 된다. 그림을 그리며 아래의 예시를 보면 이해가 될 것 같긴 하지만 안되어도 두 번째 방법이 있다.

 

1의 갯수가 a, 2의 개수가 b일 때 2의 개수 b는 0개부터 둘 수 있는 최대 개수까지 늘려가며 (a+b)C(b) * 2^(b) 를 모두 더했다.

 

아래와 같이 했다고 보면 된다.

1. N = 1일 때, 1C0 = 1

2. N = 2일 때, 2C0 + 1C1 * 2 = 3

<여기서 1C1이 된 이유는 1의 개수가 0, 2의 갯수가 1일 때 놓을 수 있는 방법이기 때문이다.>

3. N = 3일 때, 3C0 + 2C1 * 2 = 5

4. N = 4일 때, 4C0 + 3C1 * 2 + 2C2 * 2 * 2 =11

...

 

이런 식으로 늘려 가다 보면 b = N//2 까지만 증가하는 것을 알 수 있게 되고, 아래와 같이 코드를 작성했다.  

import sys

sys.setrecursionlimit(10**9)
N = int(sys.stdin.readline())
table = {}
mod = 10007

def solve(total, two):
	if (total, two) in table.keys():
		return table[(total, two)]
	if total == 0 or two == 0 or total == two:
		table[(total, two)] = 1
		return 1

	ret = (solve(total - 1, two - 1) + solve(total - 1, two)) % mod
	table[(total, two)] = ret
	return ret

answer = [(solve(N - x, x)*(2**x)) for x in range(N//2 + 1)]
sys.stdout.write(str(sum(answer) % mod))

 

두 번째 방법.

첫 번째 방법보다 훨씬 간단하다.

 

이 코드의 아이디어는 간단하다. 2xN의 타일링을 위해서는 총 세 가지 경우가 존재하게 된다.

1. 2x(N-1)만큼 타일링하고 2x1 타일을 붙인다.

2-1. 2x(N-2)만큼 타일링하고 1x2 타일을 두 개 붙인다.

2-2. 2x(N-2)만큼 타일링하고 2x2 타일을 한 개 붙인다.

 

따라서 2xN에 타일링할 수 있는 경우의 수를 dp(N)이라 할 때, dp(N) = dp(N-1) + dp(N-2) * 2 가 된다. 코드는 아래와 같이 작성을 했으며 첫 번째 방법을 이해 못 했다면 이 방법을 이해하고 보면 이해가 될 것 같다.

 

import sys

N = int(sys.stdin.readline())
dp = [0, 1, 3]
for i in range(3, N+1):
	dp.append((dp[i-1] + dp[i-2]*2)%10007)
sys.stdout.write(str(dp[N]))

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다