[프로그래머스] Swift - 멀리 뛰기 (LV.2)

👆문제풀러 가기👆

문제 설명

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 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	result
4	5
3	3

 

풀이 [ 메모리: 16.5mb, 최대시간:  0.02ms ] 

func solution(_ n:Int) -> Int {
    var dp = Array(repeating: 1, count : n+1)

    if n < 2 { return dp[n] }

    for i in 2...n {
        dp[i] = (dp[i-1] + dp[i-2]) % 1234567
    }

    return dp[n]
}

 

문제를 받고 생각한 것.

1. 문제가 굉장히 단순해보이면서 불친절해 보였기 때문에, 규칙 찾기 문제라고 생각했다.
2. 그리고 규칙찾는 문제는 주로 DP문제에서 많이 나왔기 때문에 DP라고 생각했는데, 이걸.. DP라고 할 수 있을까? 라는 생각이 들었고 사실상 점화식 연습용 문제라고 생각한다. 내게 필요한 연습.
3. 1칸일 때, 1가지, 2칸일 때 2가지, 3칸일 때 3가지, 4칸일 때 5가지, 5칸일 때 8가지로
4. 1칸 + 2칸의 경우의 수의 합 = 3칸의 경우의 수
5. 2칸 + 3칸의 경우의 수의 합 = 4칸의 경우의 수
6. 위의 과정을 반복