💥이코테 실전문제 뽀개기💥

💻 3-4 1이 될 때까지

난이도🖤🤍🤍 | 제한시간 1초 | 메모리제한 128MB | 2018 E 기업 알고리즘 대회

---

왜 그리디인가?
최대한 값을 줄인다, 즉, 최대한 N을 K로 나누는 연산을 많이 수행한다

---

📌2020/12/30 작성 코드

# N, K 입력받기
n, k = map(int, input().split())

# 연산 횟수
count = 0
while n > 1:
    # 나누어 떨어질 때
    if n % k == 0:
        n /= k
        count += 1
    else:
        n -= 1
        count += 1

print(count)

---

🤓 문제 해설

• 다음의 과정을 반복할 수 없을 때까지 반복하면 정답을 구할 수 있다
  (1) N이 K의 배수가 될 때까지 1씩 빼기
  (2) N을 K로 나누기

• K로 최대한 많이 나눌 수 있도록 하는 것이 최적의 해를 보장한다!

---

🤓 단순하게 푸는 답안 예시

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

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

# 마지막으로 남은 수에 대하여 1씩 빼기
while n > 1:
    n -= 1
    result += 1

print(result)

---

🤓 다른 답안 예시

N이 100억 이상의 큰 수가 되는 경우를 가정했을 때에도 빠르게 동작하려면
N이 K의 배수가 되도록 효율적으로 한 번에 빼는 방식으로 소스코드를 작성한다

# 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)

---

🤔 리뷰

• 다른 답안 예시는 개인적으로 직관적이지 않아서 마음에 들지 않음. 입력 값이 크게 주어질 때에 한해 활용할 수 있을 것 같다.
• 다만 다른 답안 예시에서 '#마지막으로 남은 수에 대하여 1씩 빼기' 의 아이디어는 단순하게 푸는 답안 예시의 '#마지막으로 남은 수에 대하여 1씩 빼기' 의 코드보다 훨씬 좋다.