[ 프로그래머스 ] 멀리 뛰기 / 동적 계획법 ( Dynamic Programming )

 

 

 

 

 

 

🍄 코딩테스트 문제 풀이

프로그래머스

✍🏻 문제 풀이 github 링크

-Swift-CodingTest/프로그래머스/2/12914. 멀리 뛰기 at main · BaeJihae/-Swift-CodingTest

 

 

문제 설명

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

 

입출력 예 설명

입출력 예 #1

위에서 설명한 내용과 같습니다.

입출력 예 #2

(2칸, 1칸)

(1칸, 2칸)

(1칸, 1칸, 1칸)

총 3가지 방법으로 멀리 뛸 수 있습니다.

 

 

 

 

문제 풀이

나의 풀이

 

첫 번째 풀이 ( 정확성 : 31.3 % )

func solution(_ n:Int) -> Int {
    
    var count = 0
    var dividend = 0
    var divisor = 0
    
    for k in 0...n/2 {
        if k == 0 || ( k % 2 == 0 ) && ( k == n/2 ) {
            count += 1
        }else {
            let i = n - 2 * k
            if i < k {
                dividend = stride(from: n-k, to: k, by: -1).reduce(1) { $0 * ( $1 % 1234567 ) }
                divisor = (1...i).reduce(1) { $0 * ( $1 % 1234567 ) }
            }else {
                dividend = stride(from: n-k, to: i, by: -1).reduce(1) { $0 * ( $1 % 1234567 ) }
                divisor = (1...k).reduce(1) { $0 * ( $1 % 1234567 ) }
            }
            count += ( dividend / divisor ) % 1234567
        }
    }
    
    return count % 1234567
}

 

첫 번째 풀이는 확률과 통계에서의 "같은 것이 있는 순열"을 통해 풀어보려고 했다. 나머지 정리를 이용하여 값을 곱할 때마다 1234567로 나눈 나머지를 구하였다. 하지만, n이 2000이나 되기 때문에 어떻게 풀든 Int의 최댓값을 넘길 수 밖에 없었다.

 

두 번째 풀이 ( 정확성 : 37.5% )

 

func solution(_ n:Int) -> Int {
    
    func sol(_ n: Int) -> Int {
        switch n {
        case 2:
            return 2
        case 1: 
            return 1
        default:
            return (sol(n-1)%1234567) + (sol(n-2)%1234567)
        }
    }
    return sol(n) % 1234567
}

 

여러 경우의 수를 보다보니 점화식이 보였다. 재귀함수를 통하여 풀려고 했지만, n이 최댓값이 2000이 된다면, 최대로 반복되는 값은 2의 1998승일 것이다. 시간초과로 인해서 이 방법도 틀린 방법이었다. 한참을 고민해봐도 답이 나오질 않아 튜텨님을 찾아가 힌트를 얻어보았다.

 

세 번째 풀이 ( 정답! )

 

func solution(_ n:Int) -> Int {
    
    if n == 1 {
        return 1
    }else if n == 2 {
        return 2
    }
    
    var dp = [Int](repeating: 0, count: n)
    
    dp[0] = 1
    dp[1] = 2
        
    for i in 2..<n {
        dp[i] = ( dp[i-1] + dp[i-2] ) % 1234567
    }
    
    
    return dp[n-1] % 1234567
}

 

정답은 DP( dynamic Programming ) 으로 푸는 것이었다. 내가 푼 재귀함수에서의 풀이를 자세히 살펴보면, sol(8)을 이미 계산을 했음에도 다시 sol(8)을 계산하여야 했다. 반복적인 풀이를 막기위해 이미 계산된 값을 배열에 저장한다. 사실 sol(8)을 반복적으로 계산하지 않기 위해서는 큰 수에서 작은 수로의 계산이 아닌 작은 수에서 큰 수로 점화식을 사용하여 풀어야 했다.

 

그 과정에서 이와 같은 풀이가 DP를 이용한 풀이법이라는 것을 알게 되었다. for문에 해당하지 않는 1과 2의 값은 if 문으로 빼두고, 나머지는 점화식을 이용하여 풀었다. 풀이가 굉장히 깔끔하면서 엄청 빠른 속도로 풀 수 있었다.

 

다음에도 동적계획법 문제가 나온다면 바로 풀 수 있도록 동적계획법(DP)에 대해 공부해보자.

 

https://jihae-qu.tistory.com/entry/%EB%8B%A4%EC%9D%B4%EB%82%98%EB%AF%B9-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D-Dynamic-Programming-%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95

다이나믹 프로그래밍 (Dynamic Programming) / 동적 계획법