그리디
현재 상황에서 지금 당장 좋은 것만 고르는 방법

✅ 문제

어떠한 수 N이 1이 될 때까지 두 과정 중 하나를 반복적으로 선택하여 수해하려고 한다. 단, 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다.

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

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

입력 예시

25 5

출력 예시

2

💻 코드

N, K = map(int, input().split())

count = 0

while True:
    if N == 1 :
        break
    if N % K == 0 :
        N = N // K
        count += 1
    else:
        N -= 1
        count += 1
  
print(count)

설계

N이 K로 나누어 떨어지면 N을 K로 나누고, 나누어 떨어지지 않는다면 N에서 1을 뺀다. 이 과정을 무한루프로 진행하고 N이 1이 되면 빠져 나온다.

➕ 문제 해설

답안

N, K = map(int, input().split())

result = 0

while True:
    # target은 1에서 N까지의 수이고, K로 나눠질 수 있는 수 중 가장 큰 수
    target = (N // K) * K
    result += N - target
    N = target
    if N < K:
        break
    result += 1
    N //= K

result += N - 1

print(result)

📝 정리

• target = (N // K) * K, result += N - target 코드를 통해 일일이 1씩 빼지 않고 N이 K의 배수가 되도록 하여 효율적으로 한 번에 빼는 방식을 사용할 수 있다.