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

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

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

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

입력조건

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

출력조건

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

사고과정

• 먼저 본능적으로 while 문을 써야할 것 같은 느낌이 들었음
• 우선 N을 K로 나누어 떨어지게 만들 때 가장 연산 횟수가 줄어듦
• 그리디 '큰 수의법칙' 문제에서 인상깊었던 -1마다 빼주는 게 생각남. 
• N이 K 배수가 될 때까지 -1을 계속 빼주고 배수가 되면 K로 나누어주면서 중간에 연산 횟수를 count 해보자.
• 책의 풀이에서는 N이 100억이상의 수가 주어질 때까지의 상황도 고려해서 풀이를 제시(대단...)

풀이

1. 나의 풀이

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

while n != 1:
    # 2번째 법칙
    if n % k == 0:
        n //= k
        count += 1
    # 1번째 법칙
    else:
        n -= 1
        count += 1

print(count)

2. 책의 풀이(N이 100억 이상 조건일 때)

해당 풀이는 N이 K의 배수가 되도록 우선적으로 조건을 맞춰 준 후 K로 나누어지면서 N의 크기를 기하급수적으로 감소시키도록 함(소스코드에서 target 변수를 활용하는 부분)

n, k = map(int, input().split())
result = 0
while n >= k:
    target = (n // k) * k   # k의 배수로 만들기
    result += (n - target)  # k의 배수로 만들기까지의 -1횟수 더하기
    n = target

    if n < k:
        break
    # k의 배수 k로 나누기
    n //= k
    result += 1

# n이 k보다 작아졌을 때는 계속 -1해서 1로 만들기
result += (n - 1)
print(result)