[이코테] 1이 될 때까지 (파이썬)

출처 : 이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈 저)

문제

N이 1이 될 때까지 두 과정 중 하나를 반복적으로 선택하여 수행한다.

단, 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다.

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

예시

 

ex1)

N : 17

K : 4

결과 : 17 - 1 =16 , 16 / 4 = 4, 4 / 4 = 1    3회 수행

 

입력	출력
17 4	3

 

나의 생각

• 1씩 빼는 것보다 나누는 것이 훨씬 숫자를 줄인다.
• 최대한 많이 나누는 것이 관건이다.

나의 풀이

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

cnt = 0
while n != 1:
    if n % k == 0:
        n //= k
    else:
        n -= 1
    cnt += 1

print(cnt)

오답노트

• 문제에서 N의 범위가 10만 이하이므로, 일일이 1씩 빼도 문제는 해결 가능.
• 그러나 100억이상의 큰 수가 되는 경우 속도 느림.
• else와 else if문은 지양하는 게 좋다.
  그 이유는, 코드의 복잡성이 증가하는 문제가 있다.
  여러 조건이 복합적으로 얽혀있는 경우, 코드의 가독성이 저하되며 디버깅의 어려움이 생긴다.
  이러한 구조는 코드의 흐름을 파악하기 어렵게 만들어 실수를 유발하는 원인이 된다.

강의 솔루션

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

while True:
    # n이 k로 나누어떨어지는 수 중에 최댓값
    target = (n // k) * k
    # 1씩 뺀 결과를 한번에 더해주기
    result += n - target
    n = target

    # 더 이상 나눌 수 없을 때 탈출
    if n < k:
        break

    # k로 나누기
    n //= k
    result += 1
    
# 남은 수에서 1이 될때까지 뺴는 횟수
result += (n-1)
print(result)

정리

• 그리디 알고리즘은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'이다.