1이 될 때까지(p.99) - 그리디(이코테)

---

해설 부분은 책의 내용을 포함하고, 더 추가하여 최대한 자세하게 설명하려고 노력했습니다.

---

 

문제 설명

 

어떠한 수 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번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오. 

 

입력 조건 

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

 

출력 조건

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

 

입력 예시 1

 

25 5

 

출력 예시 1

 

2

 

입력 예시 2

 

17 4

 

출력 예시 2

 

3

 

 

 

---

 

해설(책 내용 + 추가 설명) 

 

그리디 알고리즘을 이용하는 문제이다. 그리디 알고리즘은 현재의 가장 최선의 방법을 연속적으로 선택하는 방법을 사용한다.

 

이것을 코드로 구현하면 대체로 입력된 n의 값을 줄여가면서 특정 조건을 만날 때 정답이 유추되도록 한다.

 

책에서 제공하는 코드는 이렇다. 

 

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

while True:
  # k로 나눠 떨어지지 않는 n값을 조정해 주고 그 차이만큼을 횟수에 추가 
  # 예를 들어 18 4이면 그 차이인 2만큼은 1을 두번 빼줬다고 생각.
  target = (n//k) * k # n이 k보다 작으면 몫이 0이 나올테니 break문에 걸림 
  result +=  (n - target) # n이 k로 나눠 떨어지는 수로 맞췄다면 마지막 n은 항상 1이 된다. 
  # 그렇게 n = 1을 추가하고 
  n = target # 그리고 마지막 target은 0이 되어서 break 문에 걸리게 된다. 
  
  if n < k:
    break 
  # k로 나누기 
  result += 1
  n //= k 
  
result += (n - 1) # 추가했던 n을 빼주면 정답이 된다. 
print(result)

 

n과 k를 입력받고 최종 출력할 횟수인 result를 0으로 초기화 해준다. 

 

그 후 while문을 사용하는데 for문과 while문의 차이는 반복할 횟수를 아느냐 모르느냐의 차이이다. 

 

몇번을 반복해서 result의 값을 지정할지 모르기 때문에 while문을 사용한다. 

 

target = (n//k) * k 

result +=  (n - target) 

n = target 

 

이 세줄은 n이 k에 맞춰 떨어지지 않는 수 일때 맞춰 떨어지도록 조정하기 위해서 적은 코드이다.

 

n = 17, k = 4라고 할때 

 

target = (17//4) * 4 = (4) * 4 = 16가 되서 4의 배수로 맞춰주게 된다. 

 

그리고 16은 17에서 1을 빼주었기 때문에 (n - target)을 result에 더해주어서 1을 빼준것을 횟수에 포함해준다. 

 

마지막으로 n을 target값으로 지정해준다. 

 

이렇게 n을 k의 배수값으로 지정해주게 되면 n을 k로 나누는 반복문을 수행하다 마지막에 n이 결국 1로 수렴하게 된다. 

 

코드의 주석에도 적어놓았듯이 n = 1일때 target = (1 // k) * k = (0) * k = 0이 된다. 

 

그리고 그 다음에 result += (n - target) = (1 - 0)이 되서 횟수에 1을 추가하게 되고 되고 

 

n = target = 0이 되어 if문에 있는 break문으로 반복문을 빠져나오게 된다. 

 

마지막 줄 result += (n - 1) = ( 0 - 1) 이 되어 횟수에서 앞서 더했던 1을 다시 빼주게 되어 원하는 결과를 출력할 수 있게 된다.