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

programmers.co.kr/learn/courses/30/lessons/12914

코딩테스트 연습 - 멀리 뛰기

풀이방법

1칸 까지가는경우

2칸 까지가는경우

3칸 까지가는경우를 그리다보면 중복되는 곳을 지나는 것을 느낄수 있을거에요

 

도형이 주어지고 해당 도형을 채워라 하는 문제와 같은느낌이 났어요

점화식? 을 세워서 풀수 있는 문제죠 n = n-1 + n-2 같은 공식으로요 ㅎㅎ

 

3칸일때

1칸까지 가는것에 + 2

2칸까지가는 것에 +1

모양과 비슷하거든요

더 해볼까요?

그림에서 보이는것 처럼

4칸일땐

 

3칸인 경우에 +1 만 이동하면 만족이되고

2칸인 경우에 +2를 해주면 만족이되네요

 

4칸을 이동하는 경우 = 3칸가는 경우의수 + 2칸가는 경우의수

를 하면모두 나오네요

 

점화식으로나타내면

d(n) = d(n-1) + d(n-2)

형태이고

d(1) = 1이죠

d(2) = 2까지는 입력해둬야

입력조건에서 n이 1부터 이기때문에 오류가 안날거같네용

 

이런 경우 함수의 재귀로만 이뤄지면 숫자가 커지면 느려질수가 있어서

동적 계획법을 추가해서

이미 계산된 수를 저장해두는 방식으로 사용했어요

 

이 식만세우면 간단하게 풀리는 문제에요

// 멀리 뛰기
private func solutionP12914(_ n:Int) -> Int {
    var save: [Int: Int] = [:]
    save[0] = 0
    save[1] = 1
    save[2] = 2
    
    func d(_ n: Int) -> Int {
        if save.keys.contains(n) {
            return save[n]!
        }
        save[n] = (d(n-2) + d(n-1)) % 1234567
        return save[n]!
    }
    let result = d(n)
    
    return result
}