[Greedy] 1이 될 때까지 (java)

[나의 코드]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Greedy1 {
    public int solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int result = 0;

        while (true) {
            if (N < K) {
                break;
            }
            if ((N % K) == 0) {
                N /= K;
                result++;
            }
            else {
                N -= 1;
                result++;
            }
        }

        System.out.println(result);
        return result;
    }

    public static void main(String[] args) throws Exception {
        new Greedy1().solution();
    }
}

 

이렇게 구현하면 N을 매번 체크해서 연산하기 때문에 시간 복잡도가 기하급수학적으로 증가한다.

 

[나동빈님 코드]

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int k = sc.nextInt();
        int result = 0;

        while (true) {
            // N이 K로 나누어 떨어지는 수가 될 때까지만 1씩 빼기
            int target = (n / k) * k;
            result += (n - target);
            n = target;
            
            // N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
            if (n < k) break;
            
            result += 1;
            n /= k;
        }

        // 마지막으로 남은 수에 대하여 1씩 빼기
        result += (n - 1);
        System.out.println(result);
    }

}

 

n이 k로 나누어 떨어지지 않더라도 target 변수에 몫을 저장한다.

그리고, result에 n에다 그 몫을 빼서, -1한 횟수로 저장한다.

 

예를 들어, n=10이고 k=4일 때, 10/4 = 2 -> 2 * 4 = 8 이므로 target=8이 된다.여기서 기존 n이었던 10에다가 8을 빼면 result=2가 되고,이는 -1 연산을 두번한 것이 되므로 잘 저장된 것을 알 수 있다.

 

참고로, target은 k의 배수라고 설정했으므로 그 다음 반복문에서는 당연히 n이 k로 나누어 떨어질 것이다.

 

이제, n은 k로 나누어 떨어지는 수가 되었기 때문에 연산 횟수를 1회 추가하고 n을 k로 나눈다.

 

반복문 탈출 이후에는 n이 1보다 크다면 1이 될때까지 -1 연산을 해야한다.

따라서, n에서 1을 뺀만큼을 더해주어야한다.

 

ex. n =26 k = 8 일 때, 위의 코드대로 실행하면서 내려오다보면,
반복문 탈출 직전에 n = 3 ,k = 8이기 때문에 k가 n보다 커서 반복문을 탈출하게된다.

하지만, 아직 n=1이 아니기때문에 3-1, 2-1의 연산을 통해 1을 만들어 줘야하고,

이는 result에 2번의 연산을 더해주는거나 마찬가지이다.