(Swift) Programmers 멀리 뛰기

SteadySlower·2022년 11월 30일
0

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

🚫 factorial을 사용한 풀이 (arithmatic overflow)

처음에는 아래처럼 모든 경우의 수를 더해서 문제를 풀어보고자 했습니다. 1과 2를 순서에 맞추어 나열하는 문제와 동일하므로 (1칸 이동의 횟수 + 2칸 이동의 횟수)! / (1칸 이동의 횟수)! * (2칸 이동의 횟수)!로 계산하면 답을 수할 수 있습니다.

하지만 이 경우 n이 너무 커지게 되면 factorial을 계산할 때 arithmatic overflow 에러가 발생해서 풀이가 불가능했습니다.

arithmatic overflow를 방지하기 위해서 문제에서 1234567로 나눈 값을 리턴하라고 했지만 factorial과 경우를 수를 구할 때는 곱셈 연산을 사용하므로 이 방식으로는 문제를 풀 수 없습니다.

func solution(_ n:Int) -> Int {
    func factorial(_ n: Int) -> Int {
        if n <= 1 {
            return 1
        } else {
            return (n * factorial(n - 1))
        }
    }
    
    func numOfCase(_ one: Int, _ two: Int) -> Int {
        factorial(one + two) / (factorial(one) * factorial(two))
    }
    
    var one = n
    var two = 0
    var ans = 0
    
    while one >= 0 {
        ans += numOfCase(one, two) % 1234567
        one -= 2
        two += 1
    }
    
    return ans
}

DP를 활용한 방법

문제 풀이 아이디어

따라서 이 문제는 덧셈과 뺄셈만을 활용해서 풀어야 합니다. dp를 활용하면 됩니다. 초기 값과 점화식은 아래와 같습니다.

// 초기값
f(0) = 1, f(1) = 1
// 0칸을 이동하는 경우, 1칸을 이동하는 경우 모두 1가지

// 점화식
f(n) = f(n - 1) + f(n - 2)
// n칸 이동 = n - 1칸을 이동하고 1칸 이동 + n - 2칸을 이동하고 2칸 이동

코드

func solution(_ n:Int) -> Int {
    var cache = Array(repeating: 0, count: n + 1)
    
    func dp(_ n: Int) -> Int {
        if n <= 1 {
            return 1
        }
        
        if cache[n] == 0 {
            cache[n] = dp(n - 1) + dp(n - 2)
        }
        
        return cache[n] % 1234567
    }
    
    return dp(n)
}
profile
백과사전 보다 항해일지(혹은 표류일지)를 지향합니다.

0개의 댓글