문제
https://www.acmicpc.net/problem/1904
1904번: 01타일
지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이
www.acmicpc.net
풀이
n = int(input())
d = [0]*(n+1)
d[0]=1
d[1]=1
for i in range(2,n+1):
d[i] = (d[i-1] + d[i-2])%15746
print(d[n])
d[3]
- d[2]의 숫자들의 마지막에 1을 붙인 것
- d[1]의 숫자들의 마지막에 00을 붙인 것
=> d[3] = d[2] + d[1]
d[4]
- d[3]의 숫자들의 마지막에 1을 붙인 것
- d[2]의 숫자들의 마지막에 00을 붙인 것
=> d[4] = d[3] + d[2]
이렇게 구해가다 보면 d[n] = d[n-1] + d[n-2] 라는 식이 나온다.
d[2]를 구하기 위해서 d[0]에 1을 넣어주었다.
'코딩테스트 > Python' 카테고리의 다른 글
| [Python] 백준 #1927 - 최소 힙 (0) | 2021.12.21 |
|---|---|
| [Python] 백준 #11279 - 최대 힙 (0) | 2021.12.21 |
| [Python] 백준 #1003 - 피보나치 함수 (0) | 2021.12.13 |
| [Python] 백준 #9095 - 1, 2, 3 더하기 (0) | 2021.12.12 |
| [Python] 백준 #11727 - 2×n 타일링 2 (0) | 2021.12.12 |
