해결했습니다!

제가 해결한 방법은 반복문에서 반복되는 수를 줄이는 것인데, 혹시 더 나은 방법이 있다면 알려주시면 감사하겠습니다.

저도 왜 시간초과가 뜨나 했는데 바텀업 방식으로 푸니까 쉽게 되더라구요. 재귀함수가 성능이 별로 안좋아요

바텀업 방식이 어떤식으로 푸는건지 조금 자세히 설명해주실수 있나요? 어떻게하는지 상상이 안가네요

음... 이런 문제를 DP 문제라고 불러요. 일단 제가 설명을 잘하는게 아니라 다른 분이 하신 블로그 주소 첨부해둘게요

https://semaph.tistory.com/16

피보나치를 예로 들면(1 1 2 3 5 8 13 21 34 55 )

피보나치 10을 구하래요. 피보나치 1, 2 는 값이 1이죠. 

그럼 이걸 앞에서부터 피보나치 3 은 1+1 =2

피보나치 4 는 1+2, 피보나치 5 는 3+2 이렇게 계산해주는 방식을 바텀업 방식이라고 불러요.

근데 이걸 피보나치 10은 피보나치 9+피보나치 8. 근데, 피보나치 9랑 8은 값이 따로 저장된게 없으니까 다시 한번 실행

피보나치 9 = 피보나치 8+ 피보나치 7, 피보나치 8 = 피보나치 7 + 피보나치6 ...... 이렇게 하다가 피보나치 1이랑 2가 나오면, 1이랑 1을 넣어줘서

문제를 푸는 방식을 탑다운이라 하거든요?

저도 잘하는게 아니라 설명이 너무 힘드네요 ㅠㅠ

아... 무슨말인지 이해했습니다! 얼핏 비슷한 방법이라고 생각했는데 파이썬처럼 느린 언어는 저렇게 구현하면 속도가 확실히 개선되겠네요. 감사합니다!