[백준] 1904번 01타일 / 파이썬(python)

# 문제 링크

www.acmicpc.net/problem/1904

1904번: 01타일

# Soultion(실패)

메모리 초과문제로 실패하였다.

# 메모리 초과
n = int(input())
 
li = [1,2]
 
for i in range(2,n):
    li.append((li[i-1]+li[i-2]))
print(li[n-1]%15746)

# Soultion(성공)

리스트에 저장할 때, 너무 큰 수를 넣어서 메모리초과문제가 발생하여15746을 나눈 나머지를 출력하는 방식이 아닌, 리스트에 저장할때 나머지를 저장하는 방식으로 변경

 
n = int(input())
 
li = [1,2]
 
for i in range(2,n):
    li.append((li[i-1]+li[i-2])%15746)
print(li[n-1])

 

이 문제는 피보나치수열과 똑같이 점화식을 이용하여 푸는 문제이다.

수열은 1,2,3,5,8과 같은순서로 증가한다.

따라서 재귀함수를 이용하여 문제를 풀게되면 시간이 오래걸리기때문에, for문을 이용하여 간단하게 구현