[프로그래머스] Lv. 2 - 멀리뛰기

제목: Lv. 2 - 멀리뛰기

시간: 40분

 

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

프로그래머스

 

func solution(_ n:Int) -> Int {   
    var arr = (0..<n).map{$0}
    
    if (n == 1) {return 1}
    if (n == 2) {return 2}
    
    arr[0] = 1
    arr[1] = 2
    
    for i in (2..<n) {
        arr[i] = (arr[i-2] + arr[i-1]) % 1234567
    }
    
    return arr.last!
}

 

멀리 뛰기를 하는 경우의 수를 직접 계산해보면서 나열해보면 

 

    // N = 1 : 1
    // N = 2 : 2
    // N = 3 : 3

    // N = 4 : 5
    // 1111 : 1
    // 112 : 3
    // 22 : 1

 

    // N = 5 : 8
    // 11111 : 1
    // 1112 : 4
    // 122 : 3

 

1, 2, 3, 5, 8 ... 이렇게 규칙이 생겨요.

DP로 피보나치 값을 구해 문제를 해결했어요.

 

코테할 때 점화식, 확률 공식을 생각해보는 습관이 필요해보이네요 :)

 

그리고 나머지를 맨 마지막에 계산했었는데, 값이 너무 커져서 실패가 뜨더라구요.

 

결국엔 마지막에 있는 값은 부모이고,

분모에 있는 값을 하나씩 나눈다는 생각으로 DP 계산할 때 넣어줬습니다.