멀리 뛰기 Swift

문제 설명

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.

제한 사항

• n은 1 이상, 2000 이하인 정수입니다.

내가 푼 풀이

처음에는 n은 1칸,2칸의 갯수 합, r은 2칸의 갯수로 nCr 조합의 총합을 구해서 1234567 로 나눈 값을 출력하려고 했다.

nCr = nPr / r! = n! / r!(n-r)! 이다. 이 방법을 이용하려는데 n의 최대값은 2000이다

위 공식을 이용하는데 2000!은 어마어마한 크기이고, Int로 담지 못한다.

 

다른방법은 규칙을 찾는것인데, 이 문제는 피보나치 수의 점화식을 적용할 수 있다.

n[1]= 1, n[2]= 2, n[3] = 1+ 2 = 3, n[4] = 2 + 3 = 5 ..... n[i] = n[i-1] + n[i-2]

1<= n <= 2000 인 n 역시 피보나치 수를 적용해 n번째 수는 매우매우 큰 수이다.

재귀적으로 변수 하나에 더해가는 방법보다

n크기만큼 배열을 만들어서 더한 수를 1234567로 나눈 값을 배열에 적용해서 접근하기로 한다.

피보나치 수의 성질을 이용하려면 먼저 n[1]= 1, n[2]= 2 를 넣고 3부터 적용한다.

 

func solution(_ n:Int) -> Int {
    var num = n
    var arr = Array(repeating: 0, count: n + 1)
    if n == 1 {
        return 1
    }
    arr[0] = 1
    arr[1] = 2
    
    for i in 2..<num {
        arr[i] = (arr[i-1] + arr[i-2]) % 1234567
    }
    return arr[num - 1]
}