[Python][이코테] 1이 될 때까지

조건

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행한다.

단, 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다.

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

N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오

 

입력 조건

• 첫째 줄에 N (2 ≤ N ≤ 100000)과 K(2 ≤ K ≤ 100000)가 공백으로 구분되며 각각 자연수로 주어진다. 이때 입력으로 주어지는 N은 항상 K보다 크거나 같다.
• 첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력한다.

 

입력 예시

25 5

 

출력 예시

2

 

문제를 딱 보자마자

N을 K로 나누고 나머지를 더하고 나눈 몫이 K보다 작아지면 해당 몫이 1이 될 때까지 빼는 (해당 몫 - 1을 하면 되겠다)라고 생각했다.

 

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

while(True):
    a = n // k
    b = n - (a * k)
    
    if a >= k:
        count += 1 + b
        n = a
        
    if a < k:
        count += b + 1
        break
    
if a != 1:
    count += a - 1
            
print(count)

a는 N을 K로 나눈 몫을

b는 나머지 값을 저장하고

 

몫이 K보다 크면 나눈 횟수 +1과 몫을 1씩 빼야 하는 횟수(b)를 카운트 해주고 다시 몫을 K로 나누기위해 n = a로 저장한다.

 

반복하다가 몫이 k보다 작아져서 나눌 수 없어지면

 

방금 나눈 횟수 +1과 몫을 K와 나눈 나머지 값을 더해준 후 반복문을 탈출한다.

 

이후 몫이 1이 아니면 몫이 1이 될 때까지 (a -1을 해주면 1이 될 때까지 빼야하는 횟수다) 빼준 값을 카운트에 더해준다.

 

---

 

위는 내가 직접 푼 방식으로 내가 찾지 못한 히든 케이스의 정답이 있을 수 도 있다.

 

아래는 책 저자의 정답 예시이다.

 

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
    
result += (n-1)
print(result)

위 방식은 내가 푼 방식이랑 비슷한 방법이다.