[Swift] 프로그래머스 피보나치 수(lv. 2)

[Swift] 프로그래머스 피보나치 수(lv. 2)

 

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12945

프로그래머스

 

 

2. 접근

 

피보나치 수는 항이 커질 수록 감당하지 못하는 수로 발전하는 측면이 있다. n이 10만까지 주어지기 때문에 이 부분을 잘 생각해야 한다.  문제에서는 1234567로 나눈 나머지를 반환하라고 했는데, 여기서 중요한 것은, 항상 An+1 항을 구할 때마다 1234567로 나누는 것과 구하고자 하는 An 항을 모두 구하고 나서 1234567로 구하는 것이 같은지가 문제된다.

 

결론적으로는 같기 때문에 매번 1234567을 나눈 것을 그 다음 항을 구하는 계산에 써도 답을 얻을 수 있다.

 

예를 들어 만약 5로 나눈 나머지를 구한다고 할 때, 피보나치 수열의 10번 째 항을 구해본다면 다음과 같다.

 

1, 1, 2, 3, 5, 8, 13, 21, 34, 55

10번 째 항을 5로 나눈 나머지는 0이다.

 

아래 처럼 나머지를 실시간으로 구하면서 값을 구해보면 다음과 같다.

1, 1, 2, 3, 0, 3, 3, 1, 4, 0

 

위의 피보나치 수열을 각각 5로 나눈 나머지가 수열로 나타나는 것을 알 수 있다.

어쨌든 같은 나머지를 구할 수 있게 되는 것이다. 수학적으로 설명하기는.... 내가 몰라서 하지 못하겠다.

 

그래서 아래와 같은 코드를 짜서 심각하게 많은 숫자(102자리)를 뽑아내지 않게 하였다.

 

3. 코드

func solution(_ n:Int) -> Int {
    if n == 2 {
        return 1
    }
    var number1 = 1
    var number2 = 1
    var number3 = 0
    for _ in 3 ... n {
        number3 = (number2 + number1) % 1234567
        number1 = number2
        number2 = number3
    }
    return number3 % 1234567
}