[프로그래머스] 멀리 뛰기 (Swift)

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

프로그래머스

 

한 친구가 일직선 상의 선에서 한 칸씩 혹은 두 칸씩 나아갈 수 있는데, 마지막 칸에 도달할 수 있는 경우의 수를 구하는 문제였다.

단, 1234567로 나눈 나머지 값을 구하는 문제

 

(이렇게 나눈 나머지 값을 구하는 문제의 경우, 마지막 결과 뿐만 아니라 그 전에 결과를 더할때 부터 1234567으로 나눈 값을 적용해주어야 한다. 중간에 Int 범위를 넘어갈 수 있기 때문)

 

접근 방법

 

0칸부터 시작해서 n칸까지 가는데,

i칸에서 i+1칸에 갈 수 있는 경로는 이미 현재 i+1칸에 갈 수 있는 경로 수 + i칸 까지 올 수 있는 경로 수이다.

i칸 까지 올 수 있는 경로를 저장하고 있는 배열을 dp[]라고 하면,

dp[i+1] = dp[i+1] + dp[i] 이다.

 

이건 한칸씩 이동했을 때이고,

두칸씩 이동할 때는 dp[i+2] = dp[i+2] + dp[i] 가 된다.

따라서 범위 내에서 n칸까지 이 경우를 모두 dp 배열에 반영해주면 된다.

 

그리고 dp[i]를 더할 때, dp[i] % 1234567 을 더해주는 것

 

소스코드

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