728x90
1904번: 01타일
지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이
www.acmicpc.net
N = int(input())
dp = [0, 1, 2] + [0] * (N - 2)
for i in range(3, N + 1):
dp[i] = (dp[i-1] + dp[i-2]) % 15746
print(dp[N])
피보나치 수열인것같아서 넣었는데 메모리 초과가 떴다.
범위를 확인해보니 최대범위는 1,000,000이 되는데 피보나치 수열은 일정이상만 가도 수가 많이 커져서 메모리를 많이 잡아먹는다.
dp에 할당할때 나머지값을 넣어줘서 해결하였다.
'STUDY > Algorithm' 카테고리의 다른 글
[백준] 1149 RGB거리 (0) | 2021.03.23 |
---|---|
[백준] 9461 파도반 수열 (0) | 2021.03.23 |
[백준] 9184 신나는 함수 실행 (0) | 2021.03.23 |
[백준] 17298 오큰수 python (0) | 2021.03.18 |
[SWEA] 1767 프로세서 연결하기 python (0) | 2021.03.17 |