백준 1904 풀이 (재귀함수 인척하는 점화식 풀이)

이거 문제도 파악하고 금방 식을 세웠다. 그런데 재귀함수로 풀으려 했더니 메모리 초과나고, 출력도 초과나고 난리도 아니었다.

결국에 고수분들 푼거 슬쩍 보고오니 재귀함수로 푸는게 아니었다. 낚였다.

 

사실 재귀함수를 써야할 때가 있고 재귀함수를 안써도 되는 경우가 존재한다. 예를 들어 연산이 너무 많아지는 경우에는 재귀함수를 정말 써야하는지 고민해보아야한다. 만약 재귀함수를 써야하는 경우에는 다이나믹 프로그래밍을 염두해 보고, 그래도 초과가 난다면 최대 재귀 제한을 풀어주면 된다.

import sys

sys.setrecursionlimit(재귀횟수)

 

난 점화식도 세웠고 딱히 재귀함수를 써야할 필요성이 없음에도 재귀함수로 푸는 것이라 추측하고 재귀를 놓지를 못했다.

그래서 이렇게 뻘한 삽질을 반복했다.

그래도 재귀함수에서 벗어나 for 루프로 풀어보니 금방 풀렸다. 막상 코드 짜니 너무 간단해서 허탈한 정도였다.ㅋㅋㅋㅋ

n = int(input())
memo = [0 for i in range(n+2)]
memo[0] = 1
memo[1] = 2
for i in range(2,n):
    memo[i] = (memo[i-1] + memo[i-2])%15746

print(memo[n-1])

 

결론 : 재귀함수로 풀어야하는지 고민해보기! 예상되는 재귀 연산 횟수가 과하지 않은가, DP로도 적합한가를 고민하고 재귀에 접근하자