[알고리즘] 1이 될때까지

관련 영상

영상 제목 : (이코테 2021 강의 몰아보기) 2. 그리디 & 구현
영상 링크

문제 설명

입력 = N, K
연산 1) N에서 1을 뺀다.
연산 2) N을 K로 나눈다.(N이 K로 나누어 떨어질때만 가능)
위의 연산 2개를 반복적으로 사용해서(순서 상관 없음) N을 1로 만들어라.
단, 최소의 연산 횟수를 사용해서.
출력 = 최소의 연산 횟수

문제 풀이

greedy니까 최대한 N의 크기를 줄일 수 있는 연산을 찾아가면서 문제를 푼다.

즉, 두번째 연산인 K로 나누기를 가장 우선으로 생각하면서, N이 K로 나누어 떨어질 상황을 만들기 위해서만 첫번째 연산인 1빼기를 실행한다. 물론 N이 K보다 작아지면 첫번째 연산밖에 할 수 없는 상황이 된다.

정당성 분석

이 때, 그리디는 내가 생각한 아이디어 즉, 알고리즘이 맞는 알고리즘인지 그 타당성을 입증해야한다. 음, 왠지 그럴거 같다.

나누기는 결국 빼기의 연속이니까 뭐 그런 느낌으로 증명을 해나가면 될 거 같은데 수학적으로 짠 하고 나타내기는 어렵다.

내 코드

import sys

N, K = map(int, sys.stdin.readline().split())
sum = 0 #출력값 즉, 답
while N>1:
    if N%K==0:
        N = N/K
        sum+=1
    else:
        N-=1
        sum+=1
        
print(sum)

더 배울점

영상에선 "N의 값을 줄일 때 2이상의 수로 나누는 작업이 1을 빼는 작어보다 수를 훨씬 많이 줄일 수 있다."라고 말한다. 간단하지만 깔끔한 설명이다.

또한 내 코드는 1을 빼는 연산을 한번의 연산으로 처리하지만, 영상의 코드에선 1을 빼는 연산이 반복되는 것을 계산해서 연산의 수를 줄인다.

영상의 코드

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

result = 0

while True:
	target = (n//k) * k
    	result += (n - target)
        n = target
        
        if n<k:
        	break
        result += 1
        n = n//k
        
result += (n-1)
print(result)