[Algorithm] (이코테) Greedy - 1이 될 때까지 (Python/파이썬)

▶ 문제 설명

어떠한 수 N이 1이 될 때까지 다음 두 과정 중 하나를 반복해서 수행한다. 두 과정은 아래와 같다.

1. N에서 1을 뺀다.
2. N을 K로 나눈다. (단, 나눌 수 있는 경우만 해당된다.)

예를 들어서 N이 17이고, K가 4라면 처음에는 나눌 수 없으므로 1을 뺀다. 그 뒤 16이 되면 K값 4로 나눌 수 있기 때문에 나누어준다. 그러면 4가 되는데 또 K값으로 나눠줄 수 있기 때문에 나눠주면 1 이므로 종료된다.

이때 결과는 총 3번 과정을 수행했으므로 3을 출력하면 된다.

---

▶ 입력 조건

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

---

▶출력 조건

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

---

▶ Code

# N, K공백을 기준으로 구분하여 입력 받기
n, k = map(int, input().split())

result = 0

while True:
    # N이 K로 나누어 떨어지는 수가 될 때까지만 1씩 빼기
    target = (n // k) * k
    result += (n - target)
    n = target
    # N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
    if n < k:
        break
    # K로 나누기
    result += 1
    n //= k

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

▶ Point

• 주어진 N에 대하여 최대한 많이 나누기를 수행하면 된다.
• N의 값을 줄일 때 2 이상의 수로 나누는 작업이 1을 빼는 작업보다 수를 훨씬 많이 줄일 수 있다.
• 가능하면 최대한 많이 나누는 작업이 최적의 해를 항상 보장할 수 있을지 생각해 보아야 한다.
• N이 아무리 큰 수여도, K로 계속 나눈다면 기하급수적으로 빠르게 줄일 수 있다.
• 다시 말해 K가 2 이상이기만 하며, K로 나누는 것이 1을 빼는 것보다 항상 빠르게 N을 줄일 수 있다.
• 또한 N은 항상 1에 도달하게 된다. (최적의 해 성립)