[1904] 01타일 (Python)

 

1904번: 01타일

 

처음 접근 할 때 N의 크기를 확인하지 않고 순열을 구현하여 해당 순열의 길이만큼을 출력하는 코드로 구현하려 했습니다.

 

오답코드

---

# 00과 1의 조합으로 얼마나 많은 경우의 수가 나올 수 있는가
from itertools import permutations


N = int(input())
count_00 = N//2
count_1 = N%2

count_possible = 0

for i in range(count_00+1):
    tmp = list(0 for _ in range(count_00-i)) +list(1 for _ in range(count_1+2*i))
    print(set(permutations(tmp,len(tmp))))
    count_possible += len(set(permutations(tmp,len(tmp))))
    
    count_possible %= 15746
print(count_possible)

당연히 런타임 에러가 나오게 되었고 이를 해결하기 위해 다이나믹 프로그래밍으로 접근하게 됐습니다.

 

다이나믹 프로그래밍을 어떻게 적용해야 할 지가 관건인 문제입니다.

 

본 문제를 찬찬히 따라가다 보면 점화식을 얻을 수 있게 되는데, 

dp[1] = 1

dp[2] = 2

dp[3] = 3

dp[4] = 5

...

dp[k] = dp[k-1] + dp[k-2] 가 됩니다.

 

점화식만 알게 된다면 다이나믹 프로그래밍은 쉽게 풀립니다.

 

정답 코드

---

N = int(input())
dp = [0] * 1000001
dp[1] = 1
dp[2] = 2
for k in range(3,N+1):
    dp[k] = (dp[k-1]+dp[k-2])%15746
print(dp[N])