[그리디 알고리즘] 1이 될 때까지 - 파이썬(python)

1이 될 때까지

난이도 : 下

시간 제한 : 1초 메모리 제한 : 128 MB

 

---

 

해답

 

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

while (n > 1):
    if (n % k == 0):
        n = n / k
        count = count + 1

    else:
        n = n - 1
        count = count + 1

print(count)

---

예시

 

# N, K을 공백을 기준으로 구분하여 입력 받기
n, k = map(int, input().split())
result = 0

// N이 K 이상이라면 K로 계속 나누기
while n >= k:
    # N이 K로 나누어 떨어지지 않는다면 N에서 1씩 빼기
    while n % k != 0:
        n -= 1
        result += 1
    # K로 나누기
    n //= k
    result += 1

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

print(result)

---

해설

 

나누기에 우선순위를 두어서 while 반복문 내에서 나누어 떨어지면 나누기를, 아니라면 1을 빼도록 만들었습니다.