プログラマー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が現れるため,再帰によって考慮せずに解く.
でも問題を見ると.
距離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行で解決できる.
に答える
最低コストで指定距離に到達する問題
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である.Reference
この問題について(プログラマーSummer/Winter Coding(~218)ジャンプと瞬間移動、SWIFT), 我々は、より多くの情報をここで見つけました https://velog.io/@hey_hen/프로그래머스-SummerWinter-Coding2018-점프와-순간이동-Swiftテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol