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

이지수·2021년 7월 6일

algorithm

문제 설명

N과 K를 입력받음
어떤 수 N이 1이 될때 까지 다음의 두 과정 중 한개를 반복적으로 선택하여 수행.
1. N에서 1을 뺀다.
2. N에서 K로 나눈다.(N이 K로 나누어 떨어질때만 가능)

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

문제풀이

N이 K로 나누어떨어진다면 N에서 K로 나누는 연산이 N의 값을 줄일 수 있어 연산의 횟수도 최소로 만들 수 있다.

내 코드

#N과 K를 입력받고 count는 0으로 초기화
N = int(input("N : "))
K = int(input("K : "))
count = 0

#N이 1이 될때까지 반복문 실행
while (N !=1):
    if(N % K ==0): #N이 K로 나누어 떨어지면 2번연산(N에서 K로 나누기) 수행
        N //= K
        count += 1
    
    else: #N이 K로 나누어 떨어지지않으면 1번연산(N에서 1빼기) 수행
        N -= 1
        count +=1
    

print(count)

N과 K를 입력받고 count는 0으로 초기화하고 N이 1이 될때까지 반복문 실행한다. 반복문 안에서 N이 K로 나누어 떨어지면 2번연산(N에서 K로 나누기) 수행하고 N이 K로 나누어 떨어지지않으면 1번연산(N에서 1빼기) 수행한다.

정답코드

# N, K공백을 기준으로 구분하여 입력 받기
n, k = map(int, input().split())

result = 0

while True:
    # N이 K로 나누어 떨어지는 수가 될 때까지만 1씩 빼기
    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)

result는 총 연산의 갯수이다.

target 이라는 변수에 n이 k로 나누어 떨어지지 않더라도 나누어 떨어지는 가장 가까운 수를 구할 수 있다. 즉, target은 k로 나누어 떨어지는 n이다.

n - target 은 1번 연산의 횟수를 한번에 구한 것이다.

n = target 은 -1을 수행한 이후 k로 나누어 떨어지는 가장 가까운 수인 n이기 때문에 target 을 n 에 저장한다.

n이 k보다 작을 때 더 이상 나눌 수 없기 때문에 반복문을 탈출한다.

현재 n은 k로 나누어 떨어지는 수가 되었기 때문에 연산 횟수를 1회 추가하고 n을 k로 나눈다.

(☝🏻) 반복문 탈출 이후 n이 1보다 크다면 1이 될때까지 1번연산을 해야한다.
따라서 최종연산횟수의 (지금의)n에서 1을 뺀만큼을 더해주어야한다.

ex. n =26 k = 8 일 때, 위의 코드대로 실행하면서 내려오다보면,
반복문 탈출 직전에 n = 3 ,k = 8이기 때문에 k가 n보다 커서 반복문을 탈출하게된다.
그러나 아직 n=1이 아니기때문에 3-1 = 2, 2-1 = 1의 계산을 통해 1을 만들어 주어야한다.