[java, 알고리즘, 그리디] :: 1이 될 때까지

이전글 :: 2021/02/17 - [Programming/알고리즘] - [java, 알고리즘, 그리디] :: 숫자 카드 게임

---

입력 조건

2 <= N < 100,000

2 <= K <= 100,000

public class GreedyEx03 {
    public static void main(String[] args) throws IOException {
        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 cnt = 0;

        while (N != 1){
            if(N % K == 0){
               N /= K;
               cnt++;
            }
            else{
                N -= 1;
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}

접근 방법

최대한 많이 나누기

 

타당성 검증

최대한 많이 나누기가 최적의 해를 보장한다는 것을 어떻게 알 수 있을까?

K가 2 이상이기만 하면 K로 나누는 것이 1을 빼는 것보다 항상 빠르게 N의 값을 줄일 수 있다.