[Algorithm] Greedy - ‘1이 될 때까지’

📣 학습한 내용을 정리한 글입니다.

Greedy Algorithm 문제입니다. 문제에 대한 내용과 풀이 그리고 결과를 간단하게 작성하였으니 참고바랍니다.
풀이 언어 : Python

문제 설명

---

내용

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

1. N에서 1을 뺀다.
2. N을 K로 나눈다.
   N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오.

입력

N(1 <= N <= 100,000)과 K(2 <= K <= 100,000)가 공백을 기준으로 하여 각각 자연수 입력받는다.

출력

N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야하는 횟수의 최솟값을 출력받는다.

문제 풀이

---

Greedy Algorithm 참고내용

• 일반적인 상황에서 Greedy Algorithm은 최적의 해를 보장할 수 없을 때가 많다.
  
• 하지만 Coding Test에선 일반적으로 Greedy Algorithm문제에서 이를 사용해 얻은 해가 최적의 해가 되는 경우가 많다.
  위 참고사항을 준수하며, 풀어보자.
  
• N을 K로 나눌 수 있는 만큼 최대한 나눈 후 count를 구한다. 즉, N을 1로 만들기 위해서 K로 나눌 수 있을 만큼 많이 나눠야 1에 더 가까워진다.
  (반복문을 이용한 솔루션 생각해야됨..)

작성 코드

Python

---

참고 : ‘동빈나’님의 (이코테 2021 강의 몰아보기) 2. 그리디 & 구현 영상

---