<문제>
어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 합니다. 단, 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있습니다.
1. N에서 1을 뺍니다.
2. N을 K로 나눕니다.
N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하세요.
<제출>
n, k = map(int, input().split())
cnt = 0
while True:
target = (n // k) * k
cnt += (n - target)
n = target
if n < k:
break
cnt += 1
n //= k
cnt += (n - 1)
print(cnt) <코드 설명>
그리디 알고리즘. 탐욕 알고리즘은 현재 상황에서 지금 가장 좋은 것만을 고르는 방법입니다.
연산 중 큰 연산은 작은 연산의 배수일 때 큰 연산을 우선으로 최대한 많이 하고 작은 연산을 하면 됩니다. 이 방법을 위 문제에 적용한다면 k로 나누기 연산을 최대한 많이 해야 합니다.
💡의사 코드
- n, k값 입력 받기
- 총 연산 수를 의미하는 cnt변수 전역 변수로 선언
- 반복문
-1 ~ n 중 가장 큰 k의 배수 찾기
-위 수와 n의 차이 만큼 cnt + 1하고 n을 가장 큰 k의 배수로 바꾸기(나눠 떨어지는 수)
-n이 k보다 작다면 나누기가 불가능하므로 반복문 탈출
-나누기가 가능하면 cnt + 1하고 n을 k로 나눈 몫으로 바꾸기 - 탈출 했을 때 n이 1이 되도록 n에서 1을 빼주는 연산
- cnt 프린트
여기서 포인트는
1. n값을 연산으로 직접 조정하는 게 아니라 연산 결과를 대입하는 것
2. target = (n // k) * k -> n이 k로 나누어 떨어지지 않을 때 k로 나누어 떨어지는 가장 가까운 정수를 찾을 수 있다.
3. cnt += (n - target) -> 1을 빼주는 연산을 몇 번 수행할지 한 번에 더해준다.
4. n = target -> n이 target이 된다.
이렇게 코드를 작성하면 반복문 한 스텝당 n이 k로 나누어지는 연산이 바로 수행되기 때문에 반복 횟수마다 기하급수적으로 n값이 줄어듭니다. 즉 로그 시간 복잡도를 가집니다.
<메모>
처음에 매번 빼주고 곱해주는 조건문으로 제출했었는데 최대한 묶어서 생각하는 방법을 배우자.
