[백준] 11726번 타일 쌓기 문제 - DP로 풀 수 있었잖아

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

11726번: 2×n 타일링

dp로 풀려다가 

타일 앞에 눕힌 것(2), 세운 것(1) 씩 추가해주면

이전 dp[n - 1] 앞에만 붙이면 되는 거였는데..

대칭 구조까지 생각하고 복잡하게 생각해서

단순 구현했다.

 

---

1. 수학적으로 풀이 - 중복순열

 

아래아 같이

1과 2을 더하는 순서를 고려해서 n을 만드는 갯수를 구해보자.

1. n을 2로 나눈(//)수를 two_mod
2. 0, 1, 2, 3, ... two_mod까지

2. 중복순열 갯수 세기
1) 2의 갯수 two_num
1의 개수는 n - two_num이기 때문에
two_num! (n - two_num)! / n! 으로 구하면 된다구
2) 각각의 값을 더한다.

예시: n = 2
0: 2! // 2! = 1
1: 2! // 1 
즉, 1 + 1 = 2

 

# BOJ_11726
from math import factorial
import time

# 입력
n = int(input())
start = time.time()
# n을 1과 2의 합으로 구하는 경우의 수와 같다.
# 하지만 1과 2의 조합들을 더하는 순서 또한 고려해줘야한다
# 2로 나눈 값
two_mod = n // 2
count = 0

for i in range(two_mod + 1):
    one_num = n - (i * 2)
    total_num = one_num + i
    count += factorial(total_num) // (factorial(i) * factorial(one_num))
print(count % 10007, end=' ')
end = time.time()
print('-> running time:', round(end - start, 4), '초')

이렇게 풀어도 맞게 나오지만, 너무 수학적으로 풀어서

위의 풀이 방식은

1, 2, 3의 조합으로 풀게 된다면

또는 벽의 높이가 더 늘어난다면 등

문제가 달라지면 응용이 어려울 것 같다. 

 

1000을 입력하면

1000 1115 -> running time: 0.0404 초

 다음과 같이 0.04초가 나온다.

---

 

2. DP 로 푸는 방법

1. dp[n -1] 맨 오른쪽에 타일 세로로 붙이기2. dp[n-2] 맨 오른쪽에 타일 가로로 붙이기

 

따라서 1과 2를 합해주면 되므로 아래와 같다.

# BOJ_11726_DP
import time

n = int(input())
start = time.time()
dp = [0] * 1001
dp[1] = 1
dp[2] = 2
for x in range(3, 1001):
    dp[x] = dp[x-1] + dp[x-2]

print(dp[n] % 10007, end=' ')
# print(dp[n] % 10007)
end = time.time()
print('-> running time:', round(end - start, 4), '초')

 

1000 1115 -> running time: 0.001 초

0.001초가 나온다.

dp가 수학적으로 푼 풀이보다 시간이 1.5배이상 단축되는 것을 확인했다.

그리고 심지어 메모리까지 적게 차지.. ㅎㅎ