[この珂太]グリディ-1まで

🔔 質問する

任意の数Nが1である前に、次の2つのプロセスのうちの1つを繰り返し選択して実行します.ただし,2番目の演算はNをKで割った場合にのみ選択できる.
1.Nから1を減算します.
2.NをKで割る.
例えば、Nは17、Kは4とする.このとき,1回1回のプロセスを実行するとNは16となる.その後2回の処理を行い,Nは1となる.その結果,この場合,プロセス全体を実行する回数は3であった.これはNを1にする最小回数である.
NとKが与えられると、Nが1になるまで1回または2回のプロセスを実行する最小回数を求めるプログラムを作成します.

入力

第1行N(2<=N<=10000)とK(2<=K<=10000)は、それぞれ自然数で与えられる空白に分割される.このとき入力されるNは常にK以上である.

しゅつりょく

は、Nが1になるまで、1行目に1回または2回の実行プロセスの最大値を出力する.

🎯 解答方法

この問題を解決する考えは,与えられたNに対して「できるだけ多くの区分」を実行することである.場合によっては、「2つ以上の数」が「1を減算」よりも多くの数字を減らすことができるからです.問題では,kは2以上の自然数であり,可能であれば,常により速く数字を減らす方法で割る.
例えば、Nが9の場合Kが3であれば、2回に分けてN=9からN=1に瞬時に変化する.したがって、1を迅速に生成することができる.逆に、N=9では1を減算するだけで8回減算する必要があるが、N=1を生成することができる.したがって、Kでできるだけ多く除算すると、N=1を最も速く生成することができる.
したがって,次の過程を繰り返して,繰り返しができないまで正解を得ることができる.
1.NがKの倍数になるまで1を減算
2.NをKで割る

💻 Pythonコード

n, k = map(int, input().split())

answer = 0
while n != 1:
    if n%k == 0: # n이 k로 나누어 떨어진다면
        n //= k
        answer += 1
    else:
        n -= 1
        answer += 1

print(answer)

💡 考えなければならないこと

問題の中で、Nの範囲は10万以下で、このように1つずつ取り除いても問題を解決することができます.ただし,Nが100億個以上の大数であれば,高速で実行するためには,NをKの倍数だけ効率的に減算するようにソースコードを記述しなければならない.

💻 改良されたPythonコード

n, k = map(int, input().split())
answer = 0

while True:
    target = (n//k) * k # n이 k로 나누어 떨어지지 않는 경우에 k로 나누어 떨어지는 가장 가까운 수
    answer += (n-target) # k로 나누어 떨어지는 수가 되기까지 1을 몇 번 뺐는지
    n = target

    if n < k:
        break
    n //= k
    answer += 1

answer += (n-1) # 남은 수에 대해서 1씩 빼기
print(answer)