[그리디/Greedy] 이코테 1이 될 때까지 (Python / 파이썬)

이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈 저) 3장 그리디(greedy, 탐욕법) 알고리즘의 1이 될 때까지 문제는 어떤 수 N이 주어졌을 때 1을 빼거나 K로 나누는 과정을 반복하여 N이 1이 되도록 하는 과정을 수행하는 최소 횟수를 구하는 문제이다.

 

이코테 3장 그리디 1이 될 때까지 문제 정보

출처

- [한빛미디어] 이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈 저)

- https://youtu.be/2zjoKjt97vQ

알고리즘 분류

- 그리디 알고리즘 (greedy algorithm, 탐욕법)

 

1이 될 때까지 문제 요약

• 어떤 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다.
  • 1. N에서 1을 뺀다.
  • 2. N을 K로 나눈다.
• 이때 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다.
• 첫째 줄에 N(1 ≤ N ≤ 100,000)과 K(2 ≤ K ≤ 100,000)가 공백을 기준으로 하여 자연수로 주어진다.
• N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구한다.
  

문제 풀이 과정

1. N과 K를 입력받는다.
2. 반복문을 무한으로 돌리면서
3. N보다 작거나 같고, N에서 가장 가까운 K로 나누어 떨어지는 수를 구한다.
4. 3번에서 구한 수까지 1을 반복하여 빼고(1번 과정), 횟수를 카운트한다.
5. 만약 N이 K보다 작으면 1번 과정만을 할 수 있으므로 반복문을 탈출한다.
6. 아니라면 N을 K로 나누고(2번 과정) 횟수를 1번 추가한다.
7. 반복문을 탈출한 후 N이 1보다 크다면 1이 될 수 있도록 남은 수에 대해 1을 반복하여 빼고(1번 과정), 횟수를 카운트한다.
8. 카운트한 횟수를 출력한다.

 

코드 및 설명

• N, K - 입력받은 수
• count - 과정 수행 횟수
• target - N에서 가장 가까운 K로 나누어 떨어지는 수 (target ≤ N)
• 시간 복잡도 - 로그

N, K = map(int, input().split())

count = 0

while True:
    target = (N // K) * K  # N에서 가장 가까운 K로 나눠 떨어지는 수 구하기
    count += (N - target)
    N = target

    if N < K:
        break

    N //= K
    count += 1

count += (N - 1)  # N이 1보다 크다면 1이 되도록 남은 수에 대해 1씩 빼기

print(count)

---

최대한 많이 나누기(2번 과정)를 수행하면 된다. target을 활용하는 것이 시간 복잡도를 줄일 수 있는 핵심인 것 같다. 처음에는 N이 K보다 작을 때를 고려하지 않았는데, 문제의 조건을 잘 읽어야겠다.

 

이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈 저) 3장 그리디(greedy, 탐욕법) 알고리즘의 1이 될 때까지 문제를 파이썬 python으로 풀어보았다.