1이 될 때까지 (그리디 알고리즘/실전)

1이 될 때까지

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

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

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

 

N과 K가 주어질 때 N이 1이 될 때 까지 1번 혹은 2번의 과정을 수행해야하는 최소 횟수를 구하시오.

 

 

---

입력 조건

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

 

출력 조건

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

 

입력 예시

25 5

출력 예시

2

 

 

 

---

 

 

문제 해설 

 

나는 첫번째로, 가능한 두 과정을  함수로 나누어  조건에 따라 호출하는 방법으로 구성했다.(사실 이 문제에서는 그냥  넣어주는게 더 빠를지두..그치만 함수로 풀어보고싶었다.) 다만 문제를 겼은 점을 함수 안과 밖의 count 변수가 이어지지않앗다는 점이다. 이는 함수안에 global count를 넣으므로 이어줄 수 있었다. 

 

두번째로 책에서 제시한 방법은 나눠질 때까지 빼고 나머지를 하나씩 빼주는 것이다. 자세한 것은 아래의 코드를 참고하기를 바란다. N>=K라면 계속 나눌 수 있는 상황이 나온다는 것만 기억하면 된다.

 

 

---

 

코드

 

첫번째 방법

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

def first(n):
    n-=1
    global count
    count += 1
    return(n)

def second(n,k):
    n = n/k
    global count
    count += 1
    return(n)

while(n>1):
    while(n%k==0):
        n = second(n,k)
    if(n==1):
        break
    else:
        n = first(n)

print(count)

 

 

두번째 방법'

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

while (True):
    target = (n//k)*k
    count += n - target
    n = target

    if n<k:
        break
    else:
        n //= k
        count += 1

count += n-1
print(count)