1이 될 때까지-[이것이 취업을 위한 코딩 테스트다]

문제

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

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

  입력 조건

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

  출력 조건

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

코드

My answer

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

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

Another answer

# 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씩 계속 빼야하기 때문에 매우 비효율적이다. 모범답안의 경우 우선 입력받은 ,n과 가장 가까운 k의 배수를 구한다. 그럼 그 k의배수까지는 나누기로만 갈 수 있기 때문에 이제 그 나머지만큼만 1씩 빼주면된다. 예를 들어 숫자가 29 3이 들어올 경우

내 코드는 29가 3으로 안나눠지니까 1뺴고, 또 1빼고, 3으로 나누고 또 3으로 나누고 이런식이라면

모범답안은 29를 3으로 나누면 몫이 9가 나오고 다시 3을 곱하면 27까지는 나누기만으로 갈 수 있으므로 29-27=2만 1씩 뺴주면 된다라는 방식으로 접근한것이다.

숫자가 작을 때는 내 방식이 더 간단해보이지만, 코테를 풀려면 이러한 매우 큰 수의 경우도 생각해야 한다.