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

안녕하세요 :)

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

오늘도 DFS 문제를 가져왔네요 ...

풀이

숫자 (1, 2)를 이용해서 n을 만드는 경우의 수를 메모제이션 하면서 구하는 문제입니다.

• 숫자 0에서 시작하여 DFS로 1과 2를 이용해 숫자를 만들어 갑니다.

dfs(number + 1)
dfs(number + 2)

• 현재 숫자 number에 대한 경우의 수를 메모합니다.
  만약 메모한 내용이 있다면 메모한 내용을 return 해줍니다.

member[number] = cnt

• 현재 숫자 number와 만들 숫자 n이 같으면 답이 되는 경우이므로 1을 return 해줍니다.
  만약 number가 n보다 크다면 답이 되지 않는 경우이고 종료해야 하므로 0을 return 해줍니다.

이 문제의 경우 메모제이션이 필수! 입니다.

import Foundation

func solution(_ n:Int) -> Int {
    var memo: [Int: Int] = [:]
    
    func dfs(_ number: Int) -> Int {
        if let count = memo[number] {
            return count
        }
        if number == n { return 1 }
        
        if number > n { return 0 }
        
        var cnt = 0
        cnt += dfs(number + 1) % 1234567
        cnt += dfs(number + 2) % 1234567
        memo[number] = cnt
        
        return cnt
    }
    
    return dfs(0) % 1234567
}