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

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

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

11726번: 2×n 타일링

우선 이 문제를 풀 때 두 가지 방법으로 해결했다.

첫 번째 방법은 직접 푼 방법이고, 두 번째 방법은 문제를 해결하고 다른 사람들의 코드를 보니 다 똑같길래 이유를 이해하고 따라한 코드다. 두 번째 방법이 훨씬 쉽다.

 

첫 번째 방법.

우선 첫 번째 방법은 Combination을 사용했다. 그림까지 하기는 너무 오래 걸릴 것 같다.. N을 1부터 늘려가며 생각해보았다. 여기서 조합을 적용한 방법은 세로는 신경 쓰지 않고 수평선에서 길이 N을 1과 2로 채울 조합을 생각했다. 1의 갯수가 a, 2의 개수가 b일 때 2의 개수 b는 0개부터 둘 수 있는 최대 개수까지 늘려가며 (a+b)C(b)를 모두 더했다.

 

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

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

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

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

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

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

...

 

이런 식으로 늘려 가다 보면 b = N//2 까지만 증가하는 것을 알 수 있게 되고, 아래와 같이 코드를 작성했다. 물론 이 코드도 통과한 코드다. 시간이 오래 걸리긴 했지만..

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

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

	ret = (solve(left-1, right-1) + solve(left-1, right)) % 10007
	table[(left, right)] = ret
	return ret

highest = N//2 + 1
result = [solve(N-x, x) for x in range(highest)]

sys.stdout.write(str(sum(result) % 10007))

 

두 번째 방법.

두번째 방법은 첫 번째 코드로 통과한 이후 다른 사람들의 코드가 모두 동일했기 때문에 알아본 코드다. 내가 한 코드보다 훨씬 간단하며, 동적 계획법의 개념이 더 확실한 것 같다.

 

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

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

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

 

따라서 2xN에 타일링할 수 있는 경우의 수를 dp(N)이라 할 때, dp(N) = dp(N-1) + dp(N-2)가 된다. 코드는 아래와 같이 작성을 했고 그냥 더해서 리스트에 추가한 것이 전부여서 훠어어어엉ㄹㄹ씬 빠르다.

import sys

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

 

 

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