그리디 유형 문제 . 2

문제 : 1이 될 때까지

어떤 수 N이 1이 될 때까지 다음 두 과정 하나를 반복적으로 수행하려고 한다.

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

1. N에서 1을 뺀다.

2. N을 K로 나눈다.

 

즉, 다시 말해 K로 나누어 떨어지는 수가 될때까지 1씩 빼는 거다.

 

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

 

---

문제 해결 아이디어

• 주어진 N에 대하여 최대한 많이 나누기를 수행하면 최적의 해를 보장한다.
• K가 2 이상이기만 하면, K로 나누는 것이 1을 빼는 것보다 항상 빠르게 N을 줄일 수 있다.

---

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

result = 0

while True:
    target = (n // k) * k      # "테크닉" : n과 가장 가까운 K의 배수 찾는 스킬
    result += (n - target)     # 1을 빼는 횟수를 계산해서 result에 대입
    n = target
    
    if n < k:                # n이 나누는 수인 k보다 작으면 반복문 탈출
    	break
       
    result += 1
    n //= k
    
result += (n - 1)        # 마지막으로 남은 수를(k보다 작은 n)  1이 될때까지 뺀 횟수
print(result)

 

 

[ 문제 : target = (n // k) * k  이 코드의 의미를 설명하시오 ]

 

 

참고 : https://www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3