1904번: 01타일
지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이
www.acmicpc.net
[코드]
N = int(input())
dp = [0] * 1000001
dp[1] = 1
dp[2] = 2
for i in range(3, N + 1):
dp[i] = (dp[i-1] + dp[i-2])%15746
print(dp[N]%15746)
[의문]
메모리초과, 시간초과 어떻게 해결하였는지
[해설]
길이가 i인 수를 만든다고 생각해보자. 그러면 사용할 수 있는 숫자 카드는 00과 1이다. 즉, 이전에 만든 수에다가 00을 붙이거나, 1을 붙여서 만든다는 얘기가 된다. 그런데 잘 생각해보면 00은 길이가 2이기 때문에 i-1번째에서는 붙일 수가 없다. 따라서 i-2번째에서 00을 붙여 만드는 경우와 i-1번째에서 1을 붙여 만들 수 있는 경우의 합이다.
[출처] [백준] 1904 - 01타일|작성자 occidere
'코딩테스트 준비 > [백준]' 카테고리의 다른 글
| [백준]11057번 - 오르막 수 (파이썬) (0) | 2021.05.08 |
|---|---|
| [백준]11726번 - 2×n 타일링 (0) | 2021.05.08 |
| [백준] 2193번 - 이친수 (0) | 2021.05.07 |
| [백준] 1463번 - 1로 만들기 (0) | 2021.05.07 |
| [백준] 11055번 - 가장 큰 증가부분 수열 (0) | 2021.05.01 |