1이 될 때까지

- 문제

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 수행.
1. N에서 1을 뺀다.
2. N을 K로 나눈다. (단, 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

- 문제 풀이

해당 문제는 그리디 알고리즘을 적용하면, 쉽게 풀 수 있다. 내가 문제에 접근한 방법은, 조건문을 사용하는 방법이다. 1번과 2번의 방법 중, 수행 횟수가 최소가 되기 위해서는 2번을 최대한 많이 수행하는 것이 핵심이다. 어떤 수에서 '1을 빼는 것'보다, '2 이상의 수로 나누는 것'이 숫자를 훨씬 더 많이 줄일 수 있다.

프로세스를 순차적으로 나열해보면,
1. N이 K로 나누어떨어지지 않는다면 1을 빼기
2. N이 K로 나누어떨어지면 K로 나누기
3. 수행 횟수를 출력

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

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

print(count)

- 추가 설명

책에서는 조금 다르게 코드를 작성했다. 문제 접근 방식은 같지만, 어떤 코드가 더 효율적인가에 대해서는 잘 모르겠다.

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

while n >= k:
    while n % k != 0:
    	n -= 1
        result += 1
    
    n //= k
    result += 1
    
while n > 1:
    n -= 1
    result += 1

print(result)

두 번째로는 앞서 제공한 방법보다 효율적인 방법을 제시했다.

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

while True:
    target = (n // k) * k
    result += (n - target)
    n = target
    
    if n < k:
    	break
    
    result += 1
    n //= k
    
reslut += (n - 1)
print(result)

먼저, N보다 작은 K의 배수 중 가장 큰 값을 구하고 target에 저장한다. 이후 N에서 target 값을 빼면, 1번 방법을 수행하는 횟수를 구할 수 있다. 이 방법은 주어진 N의 범위보다 훨씬 큰 경우에 효율적으로 답을 구할 수 있다.

출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬, 나동빈 지음