백준 1904: 01타일 (Python)

 

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

1904번: 01타일

 

 

피보나치 수열이랑 똑같은 간단한 문제였다

그러나...

 

첫 번째 코드 - 메모리 초과

n = int(input())

d = [0] * (n + 1)
d[1] = 1
d[2] = 2

for i in range(3, n+1):
    d[i] = d[i-1] + d[i-2]

print(d[n] % 15746)

 

두 번째 코드 - 나머지 계산을 반복문 안에 넣어줌. 런타임 에러

n이 1일 때 d[2] = 2에서 인덱스 오류가 난다는 것을 발견... 왜 생각을 못했을까

n = int(input())

d = [0] * (n + 1)
d[1] = 1
d[2] = 2

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

print(d[n])

 

세 번째 코드 - 아예 리스트 크기를 문제의 범위로 잡아줌

이 와중에 0 하나 빠뜨려서 또 런타임 에러 났었다..ㅋㅋㅋㅋㅋㅋㅋ

n = int(input())

d = [0] * 1000001
d[1] = 1
d[2] = 2

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

print(d[n])

드디어 성공..

 

ㅎ;