이코테-chapter3: 그리디 1이 될 때까지

정리 내용

문제 설명

• 난이도: 하
• 시간 제한:1초
• 메모리 제한: 128mb
• 어떠한 수 n이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다.
• 단, 두 번째 연산은 n이 k로 나누어떨어질 때만 선택할 수 있다.

1. n에서 1을 뺀다.
2. n을 k로 나눈다.

• n과 k가 주어질 때, n이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구해라.

문제 풀이

• 그리디 알고리즘을 활용
• 주어진 n에 대하여 '최대한 많이 나누기'를 수행하면 된다.

코드

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

while True:
    # n == k로 나누어떨어지는 수가 될 때까지 1씩 빼기
    target = (n//k) * k
    result += (n - target)
    n = target
    # n이 k보다 작을 때(더 이상 나눌수 없을 때) 반복문 탈출
    if n < k:
        break
    # k로 나누기
    result += 1
    n //= k

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

출처 & 깃허브

이것이 취업을 위한 코딩 테스트다 with python

github