プログラマーSummer/Winter Coding(~218)ジャンプと瞬間移動、SWIFT


https://programmers.co.kr/learn/courses/30/lessons/12980
に答える
最低コストで指定距離に到達する問題
1.タイムアウト
総距離が1の場合、1マスジャンプしなければならないので、料金は1
総距離が2の場合、1コマ移動して瞬時移動、料金は1
総距離が3の場合は1コマ移動して瞬時に1コマ移動する料金は2
総距離が4の場合、距離が2の場合は順江移動すればよい.したがってコスト1
総距離が5の場合、距離が4の場合は1マスだけ移動するのが最低料金です.したがって、コストは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と結果
N:結果が出てみると
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
2進数で表すと1の個数と同じなので,本問題はSWIFTの1行で解決できる.
n.nonzeroBitCount
nonzeroBitCountは整数0ではなく戻りビット数のpropertyである.