[이취코테] 1이 될 때까지

https://youtu.be/2zjoKjt97vQ

이 문제의 해설 영상이다.

문제

어떠한 수 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번의 과정을 수행해야 하는 횟수의 최솟값을 출력한다. 

 

나의 코드

n, k = map(int, input().split())
cnt = 0
while(n != 1):
    if(n % k == 0):
        n /= k
        cnt += 1
    else:
        n -= 1
        cnt += 1
print(cnt)

이 문제는 그리디 알고리즘으로 풀 수 있는 대표적인 문제이다.

풀이 방법은 N이 1이 될 때까지 while문을 실행하면서 N이 K로 나누어 떨어지면 K로 나누고, 그렇지 않으면 - 1을 하는 방식이다. 이 문제에서 핵심은 N을 K로 최대한 많이 나누는 것이다. 왜냐하면 어떠한 수가 있을 때, '2 이상의 수로 나누는 것'이 '1을 빼는 것' 보다 숫자를 훨씬 많이 줄일 수 있기 때문이다. 따라서 이는 항상 최적의 해를 보장하기 때문에 정당하다.

 

정답 코드

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

result = 0

while True:
  target = (n // k) * k
  result += n - target
  n = target
        
  if n < k:
    break

  result += 1
  n //= k
        
result += (n-1)
print(result)

정답 코드에서는 N이 100억 이상의 더 큰 수가 되는 경우를 가정했을 때도 빠르게 동작하기 위해 N이 K의 배수가 되도록 효율적으로 한 번에 빼는 방식으로 작성했다. 

target = (n // k) * k
result += n - target
n = target

위 코드를 통하여 target이라는 변수에 N이 K로 나누어 떨어지는 가장 가까운 수를 저장하였다. 또한 n과 target의 차이를 계산하여 수행 횟수에 더해주는 방식을 사용하였다.

 

배울 점

비교적 간단한 문제였지만 더 효율적으로 푸는 방법이 있었고 앞으로 알고리즘 문제를 풀고 어떻게 하면 더 효율적 일지 고민해보는 습관을 들여야겠다고 생각했다.

 

---

참고자료: 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 지음(한빛미디어)