[Greedy] 1이 될 때까지 해설

문제

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

예를 들어 N이 17, K가 4라고 가정하자. 이때 1번의 과정을 한 번 수행하면 N은 16이 된다. 이후에 2번의 고정을 두 번 수행하면 N은 1이 된다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 된다. 이는 N을 1로 만드는 최소 횟수이다.

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

코드 (반복문 사용)

// 반복문 사용
import Foundation

let input = readLine()!.split(separator: " ").map { Int($0)! }
var (n, k) = (input[0], input[1])
var result = 0

while n != 1 {
    if n % k == 0 {
        n = n / k
    } else {
        n -= 1
    }
    result += 1
}

print(result)

---

교재 보고 수정한 코드

import Foundation

let input = readLine()!.split(separator: " ").map { Int($0)! }
var (n, k) = (input[0], input[1])
var result = 0

while true {
    let remain = n % k
    result += remain
    n -= remain
    if n < k {
        break
    }
    n /= k
    result += 1
}

result += (n - 1)
print(result)

---

그리디 정당성 판단

• 최적의 해를 구하는 방법은 k로 최대한 많이 나누는 것이 최적의 해이다.
  • 이유) 1을 빼는 것 보다, k로 나누는 것이 n이 가장 빨리 작아지기 때문이다. (k가 2 이상이기 때문에)

코드 설명

1. remain은 어떤 역할인가?
   • 변수 remain은 n을 k로 나누었을 때 나머지이다.
   • 나머지는 1을 빼야하는 횟수이다. ( n = 29이고, k = 5일 때, -1 연산을 4번 수행하면, n을 k로 나눌 수 있다. 즉, 나머지만큼 빼주면 된다.)
2. while문 종료 후 result에 (n -1) 을 더하는 이유는 무엇인가?
   • while문의 종료 조건을 보면, n < k일 때 종료된다. (당연함. 나누기 연산을 수행하면 안 됨. 제대로된 결과 얻을 수 없음)
   • 자! 그럼 while문이 종료된 후 n은 1이 아닐 수도 있음
   • 따라서 n = 1이 될 때까지 result가 증가해야됨!! 따라서 result += (n-1)을 해야함.

---

알고리즘

1. n과 k를 입력 받는다.
2. n < k일 때까지 반복문을 수행한다.
   1. 1을 빼야하는 횟수를 구한다. (remain = n % k)
   2. remain만큼 result에 더한다.
   3. n에 remain을 뺀다.
   4. 만약 n < k라면, 반복문을 종료한다. (여기서 다음 연산하면, 제대로된 결과 안 나오겠죠?)
   5. n을 k로 나눈다.
   6. result에 1을 더한다. (나눴으니께)
3. result에 n - 1만큼 더한다.

---

후기

• 사실 반복문으로 풀고, 이코테 답지를 보고도 너무 헷갈리는 부분이 많았다.
• 특히 target = (n / k) * k 이 부분!
  코드를 본 순간에는 이해할 수 있을지 모르겠지만, 나중에 혼자 저런 생각을 할 수 있을까 많이 고민했다.  
  그래서 내가 이해할 수 있는 방법인 나머지로 1을 빼야하는 횟수를 구하자!로 생각을 바꿨다.
  다른 사람 코드를 참고해서 내 것으로 만드는 연습은 정말 노력이 많이 필요한 것 같다.

---

이 글은 이것이 코딩테스트다 교재를 공부하며 포스팅한 글입니다.