그리디 : 1이 될 때 까지
어떤 수 N이 1이 될 때까지 특정 연산하는 횟수를 구하는 문제
📌 문제 설명
-
n이 1이 될 때까지 아래의 두 방법을자유롭게 이용할 수 있다.
-
단 두번 째 연산은 N이 K로 떨어 질때만 할 수 있다.
방법1 : N에서 1을 뺀다
방법2 : N을 K로 나눈다 -
N과 K가 주어질 때 N이 1이 될 때 까지 1번 혹은 2번의 과정을 수행해야 하는 최소회수를 구하기
🥕입력예시
25 5
🥕출력예시
2
📌 문제 풀이
1로 만드는 최소횟수를 구해야 하므로 숫자를 작게 만드는 것에 초점을 맞추어야한다. 따라서 최대한 많이 나누는 것에 초점을 맞추면 된다. k로 n을 계속 나누며 나누어 지지 않을 때는 n이 k의 배수가 될 때까지 빼면 된다.
n,k= map(int,input().split())
result = 0
while True:
#나누어 지는 수로 만들기
target = (n//k)*k
result += (n-target)
n = target
# 더이상 못나눌 때 종료
if n<k:
break
#k로 만들기
result += 1
n//=k
#1만 남기고 빼는 횟수
result += (n-1)```
Author And Source
이 문제에 관하여(그리디 : 1이 될 때 까지), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dongzooo/그리디-1이-될-때-까지저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)