[swift] 백준 - 1003번: 피보나치 함수

1003번: 피보나치 함수

문제 푸는 데 있어 도움이 되도록 나의 풀이와 개선된 풀이를 올립니다.
또한 풀이 후 다른 사람의 풀이를 보고 참고할만한 풀이도 올립니다.
- 문제에 따라 나의 풀이만 있을 수 있습니다.
- 해당 풀이들은 풀이 중 하나일 뿐 최선의 풀이는 아닐 수 있습니다.

 

---

 

나의 풀이

let input = Int(readLine()!)!
var arr: [Int] = Array(repeating: 0, count: 42)
arr[0] = 1
for i in 2...41 {
    arr[i] = arr[i-1] + arr[i-2]
}
for _ in 0..<input {
    let num = Int(readLine()!)!
    if num == 0 { print("1 0") }
    else { print(arr[num], arr[num+1]) }
}

 

해당 문제는 다이나믹 프로그래밍(DP)을 사용하기 위한 문제다.

DP란 값을 저장하여, 저장한 값을 이용해 문제를 풀어가는 방식인데

이를 메모이제이션 기법이라한다.

동일한 계산 반복을 저장해 놓음으로써 반복 수행 속도를 빠르게 한다.

 

해당 문제는 피보나치수를 미리 만들어 저장해 둠으로

정답의 패턴을 파악해 알맞은 피보나치수를 출력하여 풀었다.

---