[알고리즘] 1이 될 때까지 (그리디 알고리즘)

1이 될 때까지

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

 1. N에서 1을 뺀다.
 2. N을 K로 나눈다.

예를 들어 N이 17, K가 4라고 가정하자. 이때 1번의 과정을 한 번 수행하면 N은 16이 된다. 이후 2번을 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씩 빼는것보다, 나누는게 무조건 더 숫자가 빠르게 줄어들기 때문에,,

그래서 처음 코드는, 나누어 떨어지면 나누고, 아니면 1을 빼는 코드를 작성하였는데,,

 

문제에서는 N의 범위가 10만 이하이므로 이처럼 일일이 1씩 빼도 문제를 해결할 수 있다. 하지만 N이 100억 이사으이 큰 수가 되는 경우를 가정했을 때에도 빠르게 동작하려면, N이 K의 배수가 되도록 효율적으로 한 번에 빼는 방식으로 소스코드를 작성할 수 있다.

 

더 나은 방법으로 푼 코드이다.

/**
 * 1이 될 때까지
 *
 * 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다.
 * 단 두 번째 연산을 N이 K로 나누어떨어질 때만 선택할 수 있다.
 *
 * 1. N에서 1을 뺀다.
 * 2. N을 K로 나눈다.
 *
 * 예를 들어 N이 17, K가 4라고 가정하자. 이때 1번의 과정을 한 번 수행하면 N은 16이 된다. 이후 2번을 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번의 과정을 수행해야 하는 횟수의 최솟값을 출력한다.
 *
 *
 */
public class Problem3 {


    private int inputNumber;  //N
    private int divideNumber; //K
    private int count;

    public static void main(String[] args) {
        Problem3 problem3 = new Problem3();
        System.out.println(problem3.solve());
    }


    public int solve(){

        setInput();
        calculate();

        return count;
    }

    private void calculate() {

        while (inputNumber != 1){

            if(inputNumber < divideNumber) {
                count += inputNumber -1;
                break;
            }

            int remain = inputNumber % divideNumber;
            
            if(remain == 0){
                divide();
                continue;
            }
            subtract(remain);
        }
    }

    private void subtract(int remain) {
        count += remain;
        inputNumber -= remain;
    }

    private void divide() {
        inputNumber /= divideNumber;
        count++;
    }


    public void setInput() {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))){
            int[] vars = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            inputNumber = vars[0];
            divideNumber = vars[1];

        } catch (IOException e) {
            e.printStackTrace();
        }
    }


}

 

 

 

 

📔 Reference

[이것이 취업을 위한 코딩 테스트다 - 나동빈]

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체