소스코드

Greedy : 숫자가 1이 될 때까지

문제

문제 정의

• 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다.
• 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.
• 과정
  1. N에서 1을 뺀다.
  2. N을 K로 나눈다.
• 위 과정을 통해, N이 1이 되도록 하는 최소 수행 횟수를 구하라.
• 예시
  • N이 17이고, K가 4라고 가정하자.
  • 이때 1번 과정을 한번 수행하면 N은 16이 된다.
  • 이후에 2번 과정을 두 번 수행하면 N은 1이 된다.
  • 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 된다.
  • 3은 N을 1로 만드는 최소 횟수이다. 이것이 정답이다.

입력조건

• 첫째줄에 N, K의 자연수가 주어지며, 각 수는 공백으로 구분된다.
  • N: 2 이상, 100000 이하
  • K: 2 이상, 100000 이하
• 항상 N은 K보다 크거나 같다.

출력조건

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

입·출력 예시

• 입력

  25 5
  

• 출력

  2
  

풀이

문제 해설

• 1번 과정(1로 빼기)보다 2번 과정(K로 나누기)를 수행했을 때, N의 크기가 가장 많이 줄어든다.
• 따라서 총 2개의 과정 중, 2번 과정을 최우선 순위로 삼아 연산을 수행하면 된다.

소스코드

public class 숫자가_1이_될_때까지 {

  public static int solution1(int n, int k) {
    int answer = 0;

    while (n != 1) {
      if (n % k == 0)
        n /= k;
      else
        n--;
      answer++;
    }

    return answer;
  }
}

시간복잡도

• solution1 의 경우
  • 정답 구하기
    • N이 K로 나누어 떨어진다면, N을 K로 나눈다.
    • 나누어 떨어지지 않는다면, N에 1을 뺀다.
    • 최악의 경우, K가 소수(1과 자기자신만 약수로 갖는 수)로 설정된다면, 1번 과정만 수행되어야 한다.
      즉, 반복문이 N번 만큼 수행된다.
    • 따라서 정답을 구하는 시간복잡도는 O(N) 이다.
  • 따라서 총 시간복잡도는 O(N) 이다.

---

• 나동빈, 『이것이 코딩 테스트다』

본 게시글은 위 교재를 기반으로 정리한 글입니다.