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

풀이

정해진 거리를 최소한의 비용으로 도착하는 문제

1. 시간초과

총 거리가 1일 때는 무조건 한칸을 점프해야 하므로 비용은 1
총 거리가 2일 때는 한칸 이동 후 순간이동 하면 비용이 1
총 거리가 3일 때는 한칸 이동 후 순간이동 후 한칸이동 해서 비용이 2
총 거리가 4일 때는 거리가 2일 때에서 순강이동을 하면된다. 따라서 비용 1
총 거리가 5일 때는 거리가 4일 때에서 한칸만 이동하는게 최소한의 비용이 된다. 따라서 비용이 2

이런식으로 풀어가면, 타겟 거리를 짝수이면 반으로 나누고 홀수이면 1을 빼는 식으로 반복하면 해법이 나온다.

처음에는 생각없이 재귀를 통해서 풀었는데, 재귀 호출 회수 때문에 core dump가 나왔다.

  var dp: [Int] = .init(repeating: -1, count: n + 1)
  dp[1] = 1

  func table(_ index: Int, _ offset: Int) -> Int {
    guard dp[index] == -1 else { return dp[index] + offset }
    if index.isMultiple(of: 2) {
      return table(index / 2, offset)
    } else {
      return table((index - 1) / 2, offset + 1)
    }
  }

2. 수정코드

while curr > 0 {        
    if curr % 2 != 0 {
       curr -= 1
       battery += 1
    }
    else {
        curr /= 2
    }
}   

3. 한줄해법?

그런데 문제를 보면
거리 N과 결과 result를
N : result 로 나타내서 쭈욱 보면

1 : 1
2 : 1
3 : 2
4 : 1
5 : 2
6 : 2
7 : 3
8 : 1
9 : 2

이런 패턴인데 거리 N을 이진 수로 보면
0001 : 1
0010 : 2
0011 : 3
0100 : 1
0101 : 2
0110 : 2
0111 : 3
1000 : 1
1001 : 2

로 N을 2진수로 봤을 때 1의 개수와 동일하다 따라서 본 문제는 Swift에서 한줄로 해결이 가능하다.

n.nonzeroBitCount

nonzeroBitCount는 정수의 0이 아닌 비트 수를 반환하는 프로퍼티이다.