📖문제

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다.

1. N에서 1을 뺀다
2. N을 K로 나눈다.

• N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오.

입력 조건

• 첫째 줄에 N(2 <= N <= 100,000)과 K(2 <= K <= 100,000)가 공백으로 구분되며 각각 자연수로 주어진다. 이때 입력으로 주어지는 N은 항상 K보다 크거나 같다.

출력 조건

• 첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력한다.

📝풀이과정

1. N이 K의 배수인지 검사한다.

2. N이 K보다 크거나 같고, N이 K의 배수가 아니면 N % K 만큼 빼고, 연산 횟수는 N % K만큼 더한다. (1번 과정 * (N % K))
   N이 K보다 작으면, N - 1 만큼 빼고, 연산 횟수는 N - 1만큼 더한다.
   (1번 과정 * (N - 1))

3. N이 K의 배수이면 N을 K로 나눈다.(2번 과정)

   만약 N이 K의 배수임에도 불구하고 1번 과정 연산을 하게 되면 연산 횟수의 최솟값을 만족하지 않는다.

4. 풀이과정 2번, 3번의 결과를 다시 N에 넣고, N이 1이 아니면 1번으로 돌아가고 1이면 결과를 출력하고 끝낸다.

⌨코드

# n, k를 공백을 기준으로 입력 받기
n, k = map(int, input().split())

answer = 0

# n이 1이 되기 전까지 반복문을 돈다.
while n != 1:
  if k <= n:
    # 3. N이 K의 배수이면 N을 K로 나눈다.
    if n % k == 0:
      answer += 1
      n //= k
      
    else:
      # 2. N이 K보다 크거나 같고, N이 K의 배수가 아니면 N % K 만큼 빼고, 연산 횟수는 N % K만큼 더한다. 
      answer += (n % k)
      n -= (n % k)
  else:
    # 2. N이 K보다 작으면, N - 1 만큼 빼고, 연산 횟수는 N - 1만큼 더한다.
    answer += (n - 1)
    n = 1

# 연산을 수행하는 횟수의 최솟값 출력
print(answer)

☺ 느낀점

이 문제 역시 금방 아이디어를 떠올릴 수 있었다. 옛날에 백준에서 이거랑 비슷한 문제를 풀었던 것 같은데 그 때는 -1연산 뿐만 아니라 +1 연산도 있어서 아이디어를 떠올리기 더 힘들었던 것 같다.
아이디어는 떠올리기 쉬웠지만, 처음에는 연산을 수행하다가 n을 k로 나눈 몫이 k보다 작아져서 결국 n < k가 되어버리는 경우는 생각하지 못했었다. n < k가 되는 경우를 처리해주지 않으면 n이 0이 되어서 while문이 무한 루프에 빠진다.
이러한 나누기 문제는 n < k인 경우도 생각해주는 걸 잊지 말자!