レベル2-ジャンプと瞬間移動


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

質問する


OO研究所は、K格(これまでの距離)を一度に前にジャンプしたり、x 2の位置に瞬時に移動したりする特殊な機能を備えた鉄鋼キットを開発し、販売している.この鉄セットはバッテリーで作動しており、瞬時移動でバッテリーの使用量を減らすことはできませんが、前にジャンプすればバッテリーの使用量はKに達します.そのため、スチールスーツを着たり移動したりする場合、瞬間移動がより効果的です.鉄鋼セット購入者は鉄鋼セットを着て距離Nのところに行きたいと思っています.しかし、バッテリーの使用量を減らすために、ジャンプをできるだけ減らしたいと思います.鉄甲バイヤーに移動する距離Nを与える場合は、溶液関数を作成して電池使用量の最高値を返します.
たとえば、距離5の場所に行きたいです.
スチールスーツを着ていると、距離5のところに行くことができ、数は多種多様です.
  • 最初の位置は0から5コマ前にジャンプして着きましたが、バッテリーの使用量は5です.
  • は、初期位置0から2マス前にジャンプした後、瞬間的に(これまでの距離:2)、x 2に対応する位置4に移動する.このとき1コマ前にジャンプすると、バッテリーの使用量は3になります.
  • 初期位置0から1コマ前にジャンプし、それから瞬間移動(これまでの距離:1)し、x 2に対応する位置に移動できるので位置2に移動します.再び瞬間移動(これまでの距離:2)すると、位置4に移動します.このとき1コマ前にジャンプすると到着し、バッテリー使用量は2です.
  • 上記3つの場合、距離が5の場所に向かうため、3つ目の場合は電池使用量が最小となるため、答えは2です.
    せいげんじょうけん
    数字N:1以上10億以下の自然数
    数字K:1以上の自然数

    解決策


    私のやり方


    初めて見た時...6がNであると仮定し、少なくとも何回移動するかを計算する難題です.
    最初は0 -> 1(0+1) -> 2(1*2) + 4(2*2) -> 5 -> 6で、3だと思っていました.
    そうじゃない0 -> 1(0+1) -> 2(1*2) -> 3(2+1) -> 6(3*2)これじゃ2が一番小さい
    よく考えてみると、ルールは見つけやすいです.6を2で割ると3になります.3を2で割ると1(瞬間移動)になり、残りの1(=移動)になります.最後に最初と残りを全部合わせると正解があります.
    def solution(n):
        ans = 0
    
        while n != 1:
            if n % 2 == 0:
                n = n // 2
            else:
                n = n // 2
                ans += 1
    
    
        return ans + 1
    このまま解けばいいんじゃないですか.他の人が解読したコードを知らない限り...

    他人のやり方

    def solution(n):
        return bin(n).count('1')
    実はよく見ると6は2進位110(2)1を足した数が2です.だから2が正解5000を見てみましょうか.1001110001000(2)プラス1の個数が5なので正解は5...