# [이.취.코] Chap 3. 그리디 - 1이 될 때까지

- Author: @mildsalmon
- Published: 2021-08-10
- Updated: 2021-08-29
- Source: http://blex.me/@mildsalmon/chap-3-%EA%B7%B8%EB%A6%AC%EB%94%94-1%EC%9D%B4-%EB%90%A0-%EB%95%8C%EA%B9%8C%EC%A7%80
- Tags: 파이썬, 한빛미디어, 이것이취업을위한코딩테스트다, 나동빈, 코딩테스트, 문제, 그리디, 풀이, 1이될때까지

---

# 1. 1이 될 때까지

- 난이도
	- 하
- 풀이 시간
	- 30분
- 시간 제한
	- 1초
- 메모리 제한
	- 128MB
- 기출
	- 2019 국가 교육기관 코딩 테스트

### A. 문제

N이 1이 될 때까지 하나를 반복적으로 선택하여 수행하려 한다. 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.

1. N에서 1을 뺀다.
2. N을 K로 나눈다.

N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하라.

##### a. 입력 조건

- 첫번째 줄에 N (2 <= N <= 100000)과 K (2 <= K <= 100000)가 공백으로 구분되며 각각 자연수로 주어진다.
	- 입력으로 주어지는 N은 항상 K보다 크거나 같다.

##### b. 출력 조건

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

##### c. 테스트 케이스

- 입력 예시

	```

	25 5

	```

- 출력 예시

	```

	2

	```
	
### B. 내 답안

```python

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

while n != 1:
	if n % k == 0:
		n = n // k
	elif n % k != 0:
		n = n - 1
	count = count + 1

print(count)

```

### C. 문제 해설

**최대한 많이 나누기**를 수행하면 된다.

##### a. 책 답안

[python-for-coding-test/5.py at master · ndb796/python-for-coding-test (github.com)](https://github.com/ndb796/python-for-coding-test/blob/master/3/5.py)

[python-for-coding-test/6.py at master · ndb796/python-for-coding-test (github.com)](https://github.com/ndb796/python-for-coding-test/blob/master/3/6.py)

# 참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

#코딩테스트 #파이썬 #나동빈 #한빛미디어 #그리디 #큰수의법칙 #문제 #풀이