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

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다.

 

문제

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

입력 예시
25 5

출력 예시
2

---

나의 풀이

N, K = map(int, input().split())

# 1. N -= 1
# 2. N //= K

num = 0
while 1:
    if N == 1:
        break
    # N이 K로 나누어 떨어지지 않으면 1번
    if N % K:
        N -= 1
    # 나누어 떨어지면 2번
    else:
        N //= K
    num += 1
print(num)

---

해설

주어진 N에 대하여 최대한 많이 나누기를 수행한다.
2 이상의 수로 나누는 것이 1을 빼는 것보다 숫자를 더 많이 줄일 수 있다.
문제에서 N의 범위가 10만 이하이므로, 일일이 1씩 빼도 문제를 해결할 수 있지만, N이 100억 이상의 큰 수가 되는 경우 N이 K의 배수가 되도록 한 번에 빼는 방식으로 코드를 수정해야 한다.

N, K = map(int, input().split())

result = 0
while 1:
    # 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)