[Greedy] 이코테 - 1이 될 때까지(py)

문제

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

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

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

 

입력 조건

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

출력 조건

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

---

풀이

아이디어

• 주어진 n에 대하여 '최대한 많이 나누기'
• => K가 2 이상이기만 하면 K로 나누는 것이 1을 빼는 것보다 항상 빠르게 N의 값을 줄일 수 있으며, N이 결국 1에 도달한다. = K로 최대한 많이 나눌 수 있도록 하는 것이 최적의 해를 보장하는 것

 

- 내 풀이

# 어떠한 수 n, 나누는 수 k
n, k = map(int, input().split())

cnt = 0

while n != 1:
  if n % k != 0:
    n -= 1
    cnt += 1
  else:
    n //= k
    cnt += 1

print(cnt)

※ 문제에서는 N의 범위가 10만 이하이므로, 일일이 1씩 빼도 문제를 해결할 수 있지만 N이 100억 이상의 큰 수가 되는 경우를 가정했을 때도 빠르게 동작하려면, N이 K의 배수가 되도록 효율적으로 한 번에 빼는 방식으로 소스코드를 작성할 수 있다.

 

- 답안

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

while True:
    target = (n // k) * k  # n이 k로 나누어 떨어질 수 있는 target 찾기
    result += (n - target)  # n에서 target까지 -1 해야하는 횟수 한 번에 더함
    n = target  # 한 번에 빼주기
    if n < k:  # n이 더이상 k로 나누어질 수 없다면 빠져나감
        break
    result += 1  # n을 k로 나눠주는 횟수 더하기
    n //= k  # n을 k로 나눠주기

result += (n - 1)  # 마지막으로 남은 수에 대해 1씩 빼기
print(result)

마지막 -1을 해주는 부분이 이해가 잘 가지 않았는데 내가 이해한 식으로는 n이 이미 1이 되었을 때도 위 코드는 target은 n을 k로 나누므로 target은 0이 되고, result 부분에서 n(1) - target(0)이므로 result에 1을 더해주게 되고 나서 n < k 조건문으로 빠져나가므로 마지막에 1을 빼줘야 하는 것으로 이해했다.

 

혼자 풀면 단순 맨 위 풀이로만 풀어왔을 텐데 확실히 책을 통해 다른 식으로 생각해 볼 수 있어 도움이 된다.

 

+) 책에 소개된 온라인 IDE인 파이썬 튜터로 돌려보면 소스코드 단계별로 실행해 볼 수 있어 훨씬 이해가 잘 된다.

https://pythontutor.com/python-debugger.html#mode=edit

Online Python compiler and debugger - Python Tutor - Learn Python by visualizing code

---

 

출처: 나동빈, 「이것이 취업을 위한 코딩테스트다 with 파이썬」, 한빛미디어, p.99~102