[이코테] 1이 될 때까지

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

https://www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=2

 

[문제]

• 어떠한 수  N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 합니다. 단, 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있습니다.
  
  1. N에서 1을 뺍니다.
  2. N을 K로 나눕니다.
• 예를 들어 N이 17, K가 4라고 가정합시다. 이때 1번의 과정을 한 번 수행하면 N은 16이 됩니다. 이후에 2번의 과정을 두 번 수행하면 N은 1이 됩니다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 됩니다. 이는 N을 1로 만드는 최소 횟수입니다.
• N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하세요.

[문제 조건]

• 풀이 시간: 15분
• 시간 제한: 2초
• 메모리 제한: 128MB
• 입력 조건: 첫재 줄에 N(1<=N<=100000)과 K(2<=K<=1000000)가 공백을 기준으로 하여 각각 자연수로 주어집니다.
• 출력 조건: 첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최솟값을 출력합니다.

---

아이디어

 -나누어 떨어지는 경우에는 나누고, 그렇지 않은 경우는 1을 뺀다 -> 그리디 알고리즘

내가 떠올린 아이디어의 정당성 검토

 -K로 한 번 나누는 상황: 연산횟수는 1회

 -1씩 K번 빼는 상황: 연산횟수는 K회

 -나누기를 할 수 있는 상황에서는 무조건 해야 연산횟수가 가장 적어진다.

 

 -책 내용 추가:

     N이 아무리 큰 수여도 2 이상의 K로 나누기만 한다면 1로 빼는 것보다 기하급수적으로 빠르게 N을 줄일 수 있다.

     문제에 K가 2 이상이라는 조건이 있다!

 

작성 코드

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

cnt = 0

while True:
  if N==1:
    break
  if N%K==0:
    N /= K
  else:
    N -= 1
  cnt += 1

print(cnt)

---

강의에 나온 예시 코드는 이렇다!

 

현재 문제 조건에서는  N과 K가 10만 이하의 작은 정수이기 때문에

내가 한 것처럼 매번 N의 값을 체크하면서 연산 횟수를 카운트해도 크게 문제되지는 않지만,

숫자가 매우매우 커질 경우에는 저렇게 N으로 나누어 떨어지는 숫자가 될 때까지 1씩 몇 번 빼야하는지 계산하여 구하는 방식을 사용하면 불필요한 연산 반복 횟수가 확 줄어들게 된다(시간복잡도가 로그시간이 됨)