♻️Greedy - 1이 될 때까지

dev_itzel_02✨·2024년 11월 13일

♻️Algorithm

목록 보기

5/12

🏷️1이 될 때까지

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

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

🔹입력 조건

첫째 줄에 N과 K가 공백으로 구분되며 각각 2 이상 100,000 이하의 자연수로 주어진다.
이때 입력으로 주어지는 N은 항상 K보다 크거나 같다.

🔹출력 조건

첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력한다.

🔹입력 예시

25 5

🔹출력 예시

🧐접근 방향

최소한의 횟수로 수행하려면 최대한 많이 나누어야 한다❗
나누려면 N이 K의 배수 or K가 N의 약수여야 한다.

N >= K 인 경우, N이 주어지면 K로 나누어 떨어지는지 확인한다.
- 나누어 떨어지는 경우
  - N을 K로 나눈다.
- 나누어 떨어지지 않는 경우
  - N보다는 작지만 N과 가장 근접한 K의 배수를 구한다.
    👉🏼 (N // K) * K
  - N이 K로 나누어 떨어지도록 만드는 것
  - N에서 K를 뺀 값이 1을 빼야하는 횟수가 된다.
    👉🏼 N % K
  - N에서 K를 뺀 후 N을 K로 나눈다.
N < K 인 경우
- 1이 될 때까지 1씩 뺀다.

📑나의 풀이

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

while(n >= k):
    # n이 k로 나누어 떨어지는 경우
    if (n % k == 0):
        n //= k # 나누기 연산 수행
        count += 1
    else: # 나누어 떨어지지 않는 경우
        count += (n % k) # 1을 빼야 하는 횟수
        n = ((n // k) * k) # 1 빼기 연산 후 k의 배수가 됨

if(n < k):
    # n에서 (n-1)을 빼주면 1이 됨
    # 즉, (n-1)은 1 빼기 연산 횟수 
    count += (n-1) 

print(count)

📑예제 답안 1

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

# N이 K 이상이라면 K로 계속 나누기
while n >= k:
    # N이 K로 나누어 떨어지지 않는다면 N에서 1씩 빼기
    while n % k != 0:
        n -= 1
        count += 1
    # K로 나누기
    n //= k
    count += 1

# N이 1이 될때까지 1씩 빼기
while n > 1:
    n -= 1
    count += 1

print(count)

📑예제 답안 2

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

while True:
    # n을 k로 나눌 수 있는 가장 가까운 배수로 만듦
    target = (n // k) * k
    # n을 target과 값이 같도록 하려면 (n-target)번 만큼 1씩 빼야함
    count += (n - target)
    n = target
    # n을 k로 나눌 수 없으면 반복문 종료    
    if n < k:
        break

    # n을 k로 나눔    
    count += 1
    n //= k
    
# 더 이상 나눌 수 없을 때, n이 1이 될 때까지 1씩 빼야함
# (n-1)번 횟수 만큼 1씩 빼면 1이 됨
count += (n-1)
print(count)