[이코테 Ch3-4] 1이 될 때까지 (그리디)

👩🏻‍💻문제설명

[이코테 Ch3-4] 1이 될 때까지 (그리디)

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

1. N에서 1을 뺀다. 

2. N을 K로 나눈다. (N이 K로 나누어떨어질 때만 선택가능)

예를 들어 N이 17, K가 4라고 가정하자. 이때 1번의 과정을 한 번 수행하면 N은 16이 된다.
이후에 2번의 과정을 두 번 수행하면 N은 1이 된다. 결과적으로 이경우 전체과정을 실행한 횟수는 3이된다. 이는 N을 1로 만드는 최소 횟수이다.
N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야하는 최소 횟수를 구하는 프로그램을 작성하시오.

입력조건

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

출력조건

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

입력 예시

25 5

출력 예시

2

✍️Idea Sketch

알고리즘 : 그리드
해법 : 주어진 N에 대하여 K로 최대한 많이 나눴을 때 가장 빠르게 N = 1을 만들 수 있다.

시간복잡도

항상 연산 1 (N에서 1을 뺀다) 만 수행하는 최악의 상황을 고려해보자. 이 경우 O(n)이며, 이 때 n은 100,000이다. 이는 1억에 한참 못 미치므로 시간 초과의 염려가 없다.

개선방안

연산 1 (N에서 1을 뺀다) 을 개선해보자. 단순 답안의 경우, N이 K로 나누어떨어지는 값이 될 때까지 N에서 1씩 차근차근 뺀다. 이를 개선하여 N에서 1을 얼마나 빼야 하는지 계산하여 한 번에 빼자. N을 K로 나눈 나머지를 N에서 빼면 된다.

✍️내 소스코드 1

단순 답안 : N에서 1씩 빼기

  import sys
  si = sys.stdin.readline
  LIMIT = 100_000

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

  for cnt in range(LIMIT):
    # 종료조건
    if n == 1:
      print(cnt)
      break

    # 연산 2
    if n % k == 0:
      n = int(n/k)

    # 연산 1 : N에서 1씩 빼기
    else:
      n -= 1

✍️내 소스코드 2

개선답안 : N을 K로 나눈 나머지를 N에서 빼기

  import sys
  n, k = map(int, si().split())
  cnt = 0

  while n > 1:  # 종료조건
      # 연산 2
      if n % k == 0:
          n = int(n / k)
          cnt += 1

      # 연산 1 : N을 K로 나눈 나머지를 N에서 빼기
      else:
          cnt += (n % k) 
          n -= (n % k)

  print(cnt if n else cnt - 1)  # n이 0인 경우 n + 1, cnt - 1