[Algorithm] 1이 될 때까지

문제

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택해 수행한다.

단, 두번째 연산은 N이 K로 나누어질 때만 선택할 수 있다.

 

1. N에서 1을 뺀다.

2. N을 K로 나눈다.

 

입력조건

N과 K가 자연수로 주어진다.

 

출력조건

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

 

풀이

수행해야하는 횟수의 최솟값을 출력해야하기 때문에 2번 연산에 우선순위를 둔다.

먼저, 나눌 수 있으면 나누고 나눌 수 없다면 나눌 수 있을 때까지 -1 연산을 계속한다.

1이 되면 멈추도록 한다.

 

import java.util.*;

class Main {
  
  public static void main(String[] args) {
    
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int k = sc.nextInt();
    sc.close();

    int cnt = 0;
    while (n > 1) {
      if (n % k == 0) {
        n /= k;
      } else {
        n--;
      }
      // n = n % k == 0? n / k : n--; 로 변경 가능한가?
      cnt++;
    }

    System.out.println(cnt);

  }

}