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

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

1. N에서 1을 뺀다

2. N을 K로 나눈다. (단, n이 k로 나누어떨어질때만 선택할수있다)

 

문제 : N과 K가 주어질때 N이 1이 될때까지 위의과정을 수행해야하는 최소횟수를 구하는 프로그램 작성

 

입력조건 : 첫째줄에 N과 K 가 공백으로 구분되며 각각 자연수로 주어지고, N > K

 

입력예시 25 5

출력예시 2

 

접근방법 > 최대한 많이 나눈다!

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

count = 0

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

print(count)

(책 풀이)

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

result = 0
while n >= k:         # n >= k 일 경우
    while n % k != 0: # n이 k로 나눠지지 않는다면
        n -= 1        # 1씩 빼고
        result += 1   # 횟수는 한번 더하고

    n //= k           # n이 k로 나눠질 경우에도
    result += 1       # 횟수는 한번 더한다

while n>1:            # n < k 일 경우
    n -= 1
    result += 1