[TC0304] [그리디] 1이 될 때까지

이코테

✅ 이것이 코딩 테스트다 - 1이 될때까지

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


def go(n, k, cnt):
    if n == 1:
        return cnt
    if n % k == 0:
        n = n // k
        cnt += 1
        return go(n, k, cnt)
    n = n - 1
    cnt += 1
    return go(n, k, cnt)


print(n, k)
cnt = go(n, k, cnt)
print("ans:", cnt)

◾ Greedy

◾ 이 문제는 1이 될 때까지 2가지의 과정 중에서 한가지의 과정을 반복하는 것이다.

◾ 많이 풀어본 문제지만 빨리 풀지를 못한다 😨

◾ 최종적으로는 최소 횟수를 return 해야한다.

◾ 빼기 보다는 나눗셈을 하는게 최소횟수에 이득이 되므로 나눗셈을 하는 것을 중점으로 해야한다.

◾ 먼저 나눗셈을 하고 그게 아닌 나머지는 n = n - 1이 되도록 밖에 둔다.

◾ 이거랑 비슷한 백준 1로 만들기 문제 풀면 왜 n = n - 1을 밖에다가 두지 싶었는데

◾ 최소횟수를 만들기에 제일 좋은 것들을 순서대로 두는 것이었다.. 이제야 깨달음.

◾ 그리고 return go() 이런식으로 해야한다.

◾ return을 까먹어서 계속 재귀 에러가 발생 ➡️ 무한 루프에 빠진다.

 

 

 

 

 

---