https://www.acmicpc.net/problem/11444
11444번: 피보나치 수 6
첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.
www.acmicpc.net
피보나치 문제다. 해당 문제 덕분에 피보나치수를 구하는 다양한 방법들 있다는 것을 알았다.
풀이
도가뉴 항등식을 이용하였다. 해당 수식을 정리하면
위와 같은 수식을 얻을 수 있다.
해당 수식을 이용하면 기존의 피보나치수를 계산하는 방법보다 훨씬 적은 수의 호출을 통해서 값을 구할 수 있다.
메모리 초과를 피하기 위해 딕셔너리를 이용하여 수를 담아내었다.
정답 코드
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import Foundation | |
| let n = Int(readLine()!)! | |
| var arr = Dictionary<Int,Int>() | |
| arr[0] = 0 | |
| arr[1] = 1 | |
| func fibonacci(n:Int) -> Int{ | |
| let check = n%2==0 ? true : false | |
| if arr[n] == nil{ | |
| if check{ | |
| let fnM1 = fibonacci(n: n/2-1) | |
| let fn = fibonacci(n: n/2) | |
| arr[n] = (fn*(2*fnM1+fn))%1000000007 | |
| }else{ | |
| let fnP1 = fibonacci(n: n/2+1) | |
| let fn = fibonacci(n: n/2) | |
| arr[n] = ((fn*fn)+(fnP1*fnP1))%1000000007 | |
| } | |
| } | |
| return arr[n]! | |
| } | |
| print(fibonacci(n: n)) |
'Problem Solving > BOJ' 카테고리의 다른 글
| [2638] 치즈 (0) | 2023.02.10 |
|---|---|
| [11779] 최소비용 구하기 2 (0) | 2023.02.10 |
| [17144] 미세먼지 안녕! (0) | 2023.02.07 |
| [4836] 춤 (0) | 2023.02.06 |
| [4485] 녹색 옷 입은 애가 젤다지? (0) | 2023.02.05 |