[프로그래머스/Swift] 점프와 순간 이동

 

https://school.programmers.co.kr/learn/courses/30/lessons/12980

프로그래머스

 

문제에서도 주어지지만 점프로 이동하는 것을 최소로 하려고 한다!

그러니까.. 최대한 순간이동을 사용해서 진행해야 한다는 것이다. 그래서 그리디 문제인가?? 생각했고 우선 DFS로 해봤다.

먼저 순간이동으로 DFS를 재귀호출하고 그다음은 1... k칸을 이동하면서 진행하도록 했는데 5000도 시간초과로 통과하지 못했다ㅋㅋ

그래서 흠... 일단 아이패드에 예제에 규칙이 있는지 적어봤다.

순간이동을 x 2 하는 것이므로 그럼 몇번 순간이동을 할 수 있지 하고 다 나눠봤다

 

5/2 = 2/2 = 1

6/2 = 3/2 = 1

500/2 = 2500/2 = 1250/2 = 625/2 = 312/2 = 156/2 = 78/2 = 39/2 = 19/2 = 9/2 = 4/2 = 2/2 = 1

 

여기서 뭔가 보인다!!

바로 나머지 값이다.

 

5/2 = 2/2 = 1

6/2 = 3/2 = 1

500/2 = 2500/2 = 1250/2 = 625/2 = 312/2 = 156/2 = 78/2 = 39/2 = 19/2 = 9/2 = 4/2 = 2/2 = 1

 

여기에 1을 더해주면 된다.

0에서는 순간이동을 할 수 없다. 무조건 +1 필수!

 

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

 

---

 

다른 사람 코드를 보는데, 재귀 함수를 사용한 분이 있었다.

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

사실 내 코드랑 다를게 없긴 한데, 이걸 재귀함수로 잘 짠 것 같다... 대다네..

홀수의 경우 나머지가 나오니까 그걸 더해준 거다!