[이취코] 1이 될 때까지

출처 : 이것이 취업을 위한 코딩테스트다 with python p.99

 

유형 : 그리디

---

1. 문제

(자세한 건 책을 참고)

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

1) N에서 1을 뺀다.

2) N을 K로 나눈다.

 

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

 

예시

25 5

예시 출력

2

 

2. 내 코드

## 내 코드
N, K = map(int, input().split())
cnt = 0

while N > 1:
    if N % K == 0:
        N = N//K
    else:
        N -= 1
    cnt += 1

print(cnt)

처음에 별 생각없이 N을 K로 나누어질 때 두 번째 연산만 가능하고 첫 번째 연산이 안 되는줄.... 그런데 연산의 최소값을 구해야 하므로, 나누어 떨어지는 조건을 먼저 걸어야 한다! 1을 빼는 것보다 2 이상의 수로 나눠야 최소 연산 횟수를 구할 수 있으니깐!

 

3. 풀이1

## 풀이 1
n, k = map(int, input().split())
result = 0

# n이 k이상이라면 k로 계속 나누기
while n >= k:
    while n % k != 0:
        n -= 1
        result += 1
    n //= k
    result += 1

# 마지막으로 남은 수에 대해 1씩 빼기
while n > 1:
    n -= 1
    result += 1

print(result)

N이 100억 이상의 큰 수가 되는 경우를 가정했을 때에도 빠르게 동작하려면, N이 K의 배수가 되도록 효율적으로 한 번에 빼는 방식의 소스코드를 작성할 수 있다. (여기서 문제 가정은 N이 10만 이하)

 

4. 풀이 2

## 풀이 2
n, k = map(int, input().split())
result = 0

while True:
	# n이 k로 나누어떨어지는 수로 만들기
    target = (n//k) * k
    result += (n-target)
    n = target

    if n < k:
        break
    result += 1
    n //= k

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