[이코테] 숫자 카드 게임

그리디 알고리즘

공부는

'이것이 취업을 위한 코딩테스트다 with 파이썬'

으로 진행했다.

이 문제를 공부하면서 하나씩 반복하는 것을 어떻게 한 번에 묶어서 해결할 수 있는지에 대한 방법을 배울 수 있었다.

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

1. N에서 1을 뺀다.

2. N을 K로 나눈다.

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

• 입력

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

• 출력

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

먼저 내가 푼 코드는 다음과 같다. 그냥 단순히 k로 나누어지면 n을 k로 나누고, 그렇지 않으면 n에서 1을 뺐다.

n, k = map(int, input().split())
total = 0
while n != 1:
    if n % k == 0:
        n //= k
        total += 1
    else:
        n -= 1
        total += 1

total

하지만 n이 100억 이상이라면 다음과 같이 1을 빼는 동작을 한 번에 수행하도록 만들어야 한다고 한다.

#P101
n, k = map(int, input().split())
total = 0
while True:
    print(total)
    target = (n//k) * k #k로 나누어 떨어지는 수를 찾기
    total += (n - target) #나누어 떨어지는 수가 될 때까지 1을 뺀 횟수를 total에 더한다.
    n = target #나누어 떨어지는 수가 될 때까지 1을 뺀 것이므로 n를 target으로 선언한다.
    if n < k:
        break
    n //= k
    total += 1

total += (n-1) #남은 수가 1이 될 때까지 1씩 뺀 횟수를 더한다

total

쓸데 없는 연산횟수가 크게 줄었다. 특히나 그리디 알고리즘을 풀 때는 이러한 사고방식이 중요한 것 같다.