🔔 문제
어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.
1. N에서 1을 뺀다.
2. N을 K로 나눈다.
예를 들어 N이 17, K가 4라고 가정하자. 이때 1번의 과정을 한 번 수행하면 N은 16이 된다. 이후에 2번의 과정을 두 번 수행하면 N은 1이 된다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 된다. 이는 N을 1로 만드는 최소 횟수이다.
N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N(2<=N<=100,000)과 K(2<=K<=100,000)가 공백으로 구분되며 각각 자연수로 주어진다. 이때 입력으로 주어지는 N은 항상 K보다 크거나 같다.
출력
첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력한다.
🎯 풀이방법
이 문제를 풀때 모래뺏기 게임을 생각하면된다. 깃발을 쓰러뜨리기 위해 최대한 많은 양의 모래를 빼가야한다. 마찬가지로 N의 값을 1로 만드는 횟수를 최소횟수로 하기 위해 최대한 N을 K로 나누는 시도를 해야한다. 이를 기반으로 코드를 짜면 다음과 같다.
코드
N,K = map(int,input().split())
count = 0
for i in range(N):
if N > 1:
if N % K ==0:
N /= K
count +=1
else:
N -=1
count += 1
else: break
print(count)