[그리디알고리즘] 문제 - 1이 될 때까지

https://youtu.be/2zjoKjt97vQ?si=fGChNeo644FV1sFd

<문제> 1이 될 때까지

출처: 동빈나 youtube

문제 해결 아이디어

• 주어진 N에 대하여 최대한 많이 나누기를 수행
• N의 값을 줄일 때 2이상의 수로 나누는 작업이 1을 빼는 작업보다 수를 훨씬 많이 줄일 수 있음

<문제> 1이 될 때까지: 정당성 분석

• 가능하면 최대한 많이 나누는 작업이 최적의 해를 항상 보장하는가?
• N이 아무리 큰 수여도, K로 계속 나눈다면 기하 급수적으로 빠르게 줄임
• 다시 말해 K가 2 이상이기만 하면, K로 나누는 것이 1을 빼는 것보다 항상 빠르게 N을 줄일 수 있음.
  • 또한 N은 항상 1에 도달하게 됨 (최적의 해 성립)

# <문제> 1이 될 때까지
#%%
n = 17
k = 4

while n != 1:
    if n % k != 0:
        n -= 1
    n //= k
    print(n)
#%% md
* 나는 이렇게 간단하게 풀었음
* 다른 숫자가 들어가면 무한 루프에 빠지게 됨... why?
#%%
n, k = map(int, input().split())
result = 0

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

# 마지막으로 남은 수에 대해서 1씩 빼기
result += (n - 1)
print(result)
    
    
#%% md
* 정답 보고 나서 내 코드 버그 수정하기...
* 내 코드는 다시 1을 빼야 하는 순간에 돌아가지 못해서 에러가 발생했던 것임. 
#%%
n, k = map(int, input().split())
result = 0

while n % k != 0:
    n -= 1
    print(n)

while n % k == 0:
    n //= k
    print(n)

#%% md
* 다시 뒤로 돌아가려면 어떻게 해야 하는가?
* 해답으로 돌아가보자
#%%
n, k = map(int, input().split()) # n = 25, k = 3이라고 가정
result = 0

while True:
    # N이 K로 나누어 떨어지는 수가 될 때까지 빼기
    # 먼저 정수 몫을 구한 다음에 다시 k를 곱한다 -> 몇 번 나눠 떨어질 수 있는지 구하기 
    # target = (25 // 3) * 3 = 24
    # target = (8 // 3) * 3 = 6
    # target = (2 // 3) * 3 = 0
    target = (n // k) * k
    
    # 그 다음에 n에서 target을 빼면 몇 번 뺴야 하는지가 나옴. 
    # result = 25 - 24 = 1
    # result += 8 - 6 = 2 -> 2+2 = 4
    # result += (2 - 0) -> 5+2 = 7
    result += (n - target)
    
    # n = 24
    # n = 6
    # n = 0
    n = target
    
    # N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
    # 처음엔 n이 더 크다
    # n 이 2이므로 while문 탈출
    if n < k:
        break
        
    # K로 나누기
    result += 1 # result = 2, 4+1 = 5
    n //= k # 24 // 3 = 8, 6 // 3 = 2

# 마지막으로 남은 수에 대해서 1씩 빼기
# result += (7 - 1) -> 6
result += (n - 1)
print(result)
    
    
#%% md
* 로그 시간 복잡도로 문제를 풀기 위해서 위와 같은 코드를 가져옴
* 일일이 n과 k를 확인한 다음에 문제를 풀어도 되지만, 그렇게 되면 시간 복잡도가 늘어남. 

---

https://github.com/Park-Minjoo/CODINGINTERVIEW_PRACTICE/tree/main/Algorithms