🫧[이코테] 그리디- (N의 값이) 1이 될 때까지

🪂 2023. 08. 02. Wednesday_ 핫써머..😎.. 🪂

---

​
* 오늘은 '이코테' 강의에서 배운 '그리디 알고리즘' 내용 정리입니다.

​

✅ 1이 될 때까지

​

👉 문제 설명

 어떠한 수 N이 1이 될때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 합니다.
단, 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있습니다.

1. N에서 1을 뺍니다.
2. N을 K로 나눕니다.

Q: 1 혹은 2 과정을 수행해야 하는 최소 횟수를 구하는 프로그램? 

✔️ 입력 조건

첫 줄에서 N(1 <= N <=100,000)과 K(2<=K <=100,000)가
공백을 기준으로 하여 각각 자연수로 주어집니다.

✔️ 출력 조건

첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는
횟수의 최소값을 출력합니다.

✔️ 입력 예시/ 출력예시

25 3/ 6

​

👉 문제 해결 아이디어

✔️ 나누어 떨어지면 최대한 많이 나누자 !

​

👉 정당성 분석

✔️ 2 이상의 수로 나누는 작업 <<< 1을 빼는 작업보다 작업수

​

👉 문제풀이

	(이 문제. 잘 못 이해서.시간 꽤나 잡아먹음ㅜㅜ잘하자.^^)
    
   # 1이 될 때까지
	
    	step 01. 입력받는 값 n, k를 공백으로 구분해 정수로 변환한다.
		step 02. result 초기화 == 최종 계산 결과를 저장한다.
    	step 03. while문
    		N이 K로 나누어 떨어지는 수가 될 때까지 빼기
    		N이 K 보다 작은지 체크 !
    		루프를 계속 돌 경우(위 조건 불만족), K로 나누기
    	step 04. 남은 수는 1씩 빼주기

​
​

그리드 깃헙 정리 👇👇👇

Python-Algorithm

---

​

⠀⠀⠀

📌 23. 08. 02

수정할 부분이 있다면, 알려주세요~!~ 😊