[백준] 1904번: 01타일 / 파이썬

문제 링크

---

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

풀이 코드

---

n = int(input())
dp = [1] * n

for i in range(1,n):
    dp[i] = (dp[i-1] + dp[i-2]) % 15746

print(dp[-1])

코드 해석

경우의 수를 살펴보면

1 자릿수 일 땐 1  1개

2 자릿수 일 땐 00,11  2개

3 자릿수 일 땐 001,100,111  3개

4 자릿수 일 땐 0000,0011,1001,1100,1111  5개

5 자릿수 일 땐 00001,00100,00111,10000,10011,11001,11100 8개

 

어라...?

피보나치수열이랑 똑같잖아?

 

그래서 DP를 사용한 피보나치수열로 풀었다.

점화식은 dp[i] = dp[i-1] + dp[i-2]이다.

 

 

 

https://woojinhong.tistory.com/255

[백준] 2193번: 이친수 / 파이썬

매우 비슷한 문제다.

 

체감 난이도: ★☆☆☆☆