[그리디 알고리즘] 이코테 - 1이 될 때까지

문제

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

1. N에서 1을 뺍니다.

2. N을 K로 나눕니다.

 

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

 

입력 조건

첫째 줄에 N(1<=N<=100,000)과 K(2<=K<=100,000)가 공백을 기준으로 하여 각각 자연수로 주어집니다. 

 

출력조건

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

 

입출력 예

17 4

3

 

25 5

2

 

 

📌해설

 

내가 작성한 코드

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

cnt = 0
while 1:
  if n == 1:
    break
  if n % k ==0:
    n //=k
  else:
    n-=1
  cnt +=1
print(cnt)

cnt를 매번 검사 마다 증가시키는 방식입니다. 

입력 조건이 최대 100,000 라서 해당 코드에 큰 문제는 없지만 아래와 같이 코드를 짜는 것이 효율적인 방법입니다. 

 

 

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

cnt = 0
target = (n//k) *k
cnt += n - target
while 1:
  if target <k:
    break
  target//=k
  cnt +=1
result = cnt + target-1
print(result)

target을 새롭게 선언해줍니다. 

target변수는 n에서 가장 가까운 k의 배수 입니다. 

n - target이라는 값은 n -=1을 해준 횟수를 의미합니다.

즉, n-=1을 통해 target까지 이동하여 cnt에 먼저 합산 해준 뒤,

k로 나눌 수 있도록 로직을 짤 수 있습니다.

 

target은 while문을 빠져나와서 

cnt(n -> target 이동 값 + k로 나눈 횟수)와 target-1(target -> 1 이동 값)을 합산해 result에 저장하고 출력합니다.

 

 

::

 

그리디 알고리즘으로 푼 방식이 물론 바로 떠오르는 직관적인 방법은 아니지만 

훨씬 효율적인 방법(log시간으로 해결 가능한 방법)이라고 할 수 있습니다.