[파이썬 알고리즘] 1이 될 때까지 문제 풀이

❓ 문제

---

[ 문제 ] 1이 될 때까지

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

단, 두번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다.

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

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

💡 문제 해결 아이디어

---

나누기 우선 수행

N의 값을 줄일 때 2 이상의 수로 나누는 작업이 1을 빼는 작업보다 수를 훨씬 많이 줄일 수 있다.

즉, 주어진 N에 대하여 최대한 많이 나누기를 수행하면 된다.

아래 예제로 알아보자.

>  N = 25, K = 3인 경우

---

0단계(초기 단계)	-	N = 25
1단계	N - 1	N = 24
2단계	N / K	N = 8
3단계	N - 1	N = 7
4단계	N - 1	N = 6
5단계	N / K	N = 2
6단계	N - 1	N = 1

최대한 많이 나누는 작업이 최적의 해를 항상 보장할까?

N이 아무리 큰 수여도, K로 나눈다면 기하급수적으로 빠르게 줄일 수 있다.

K가 2 이상이기만 하면, K로 나누는 것이 1을 빼는 것보다 항상 빠르게 N을 줄일 수 있다.

또한 N은 항상 1에 도달하게 된다.

그러므로 최적의 해가 성립하게 되는 것이다.

✔️ 파이썬 답안 예시

---

# N, K공백을 기준으로 구분하여 입력 받기
n, k = map(int, input().split())

result = 0

while True:
    # N이 K로 나누어 떨어지는 수가 될 때까지만 1씩 빼기
		# target: n이 k로 나누어 떨어지지 않을 때, k로 나누어 지는 가장 가까운 수
    target = (n // k) * k
		# result: 1을 빼는 연산을 수행할 횟수
    result += (n - target)
    n = target
    # N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
    if n < k:
        break
    # K로 나누기
    result += 1
    n //= k

# 마지막으로 남은 수에 대하여 1씩 빼기
result += (n - 1)
print(result)

🕓 시간 복잡도 분석

---

매번 n이 k로 나누어 떨어지는지 확인해서 나누거나 빼는 연산을 수행할 수도 있지만, 위의 방법을 사용한다면 한번 반복할 때마다 n을 k로 나누기 때문에 n이 빠르게 작아지게 된다.

이 말은 곧 로그 시간 복잡도가 나오게 된다는 것과 같다.

결론적으로, 위와 같이 코드를 짠 이유는 n과 k가 아무리 큰 수여도 빠르게 문제를 풀 수 있게끔 하기 위함이다.

Notice: 이 게시물은 한빛미디어의 이것이 코딩 테스트다 영상과 교재를 참고하였습니다.