[프로그래머스] 점프와 순간 이동 - DP문제

효율성 테스트까지 있는 문제로 처음 DP로 풀어야겠다고 생각하고 풀이를 시작하였다.

 

프로그래머스 점프와 순간 이동

코딩테스트 연습 - 점프와 순간 이동

 

문제는

N칸을 이동해야한다. 그러나 조건이 있다.
(현재까지 온 거리) * 2에 해당하는 위치로 순간이동이 가능하고 이 경우에는 건전지의 소비량이 들지 않는다. 그러나 K칸을 이동하게 되면 이 경우에는 K 만큼의 건전지가 소비된다. 그러므로 순간이동을 하는 것이 효율적이다.
여기서 N칸을 이동하려고 할 때, 가장 건전지의 사용량을 최소화해서 이동할 수 있는 사용량이 얼마인지 구하는 것이다.

 

처음 풀이를 시도했을 때, 문제는 어렵지 않은데 효율성이 걸려있어 DP 방식으로 생각하고 풀이를 시도했다.

당연히 bottom - top 방식으로 시도해서 접근했고 그렇게 하면 O(N)으로 해결할 수 있기 때문에 통과할 것이라고 생각했다.

 

우선 bottom - top 방식에서 점화식을 생각했던 과정을 보면 다음과 같다.

 

1️⃣2로 나누어지는 경우는 순간이동이 가능하기 때문에 1/2 칸의 건전지 소모량을 가져왔다.

2️⃣2로 나누어지지 않는 경우는 이전 칸에서 +1을 이동하기 때문에, 이전 칸에서 +1을 하였다.

3️⃣최종적으로 이 두 경우의 더 작은 값을 찾아서 대입해주었다.

 

하지만 이 방법은 정확도의 경우에는 모두 통과하였지만, 효율성의 경우에는 실패하였다.

 

처음 짰던 소스 코드를 보면 다음과 같다.

func solution(_ n:Int) -> Int {
	
    var DP: [Int] = Array(repeating: 0, count: n+1)
    
    DP[1] = 1
    
    for dis in 2...n {
        if dis % 2 == 0 { DP[dis] = min(DP[dis-1] + 1, DP[dis/2]) } 
        else { DP[dis] = min(DP[dis-1] + 1, DP[dis/2] + 1) }
    }
    
    return DP[n]
}

 

하지만 이 방법보다 더 효율적으로 접근하는 방법이 있엇다.

바로 top - bottom 방법으로 접근하는 것이었다.

 

N칸을 이동하기 위해, 생각했던 과정은 다음과 같다.

1️⃣2로 나누어 떨어지는 경우는 현재 남은 칸에서 2를 나누어주고 건전지 소모량은 그대로 두었다.

2️⃣그렇지 않은 경우는 현재 남은 칸에서 -1을 해주고 건전지 소모량을 1 증가하였다.

3️⃣이 과정을 n == 0이 될 때까지 반복하였다.

 

결국 O(logN)으로 풀 수 있었고 O(N)보다는 더 효율적인 방법이었다.

 

전체 코드는

func solution(_ n:Int) -> Int {
    var rest: Int = n
    var ans: Int = 0
    
    while rest > 0 {
        if rest % 2 == 0 {
            rest /= 2
        } else {
            rest -= 1
            ans += 1
        }
    }
    
    return ans
}