import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); // N, K를 공백을 기준으로 구분하여 입력 받기 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; // K로 나누기 result += 1; n /= k; } // 마지막으로 남은 수에 대하여 1씩 빼기 result += (n - 1); System.out.println(result); } } ======================================================================================== /* Greedy 와 같이 최대한 으로 나누고 -1씩 빼면서 했어야 했는데 아직 그리디 사용이 익숙치 않았다 그래서 냅다 내 생각대로 풀어버렸다. 다시 한번 핵심을 되짚어 보자면 최대한 큰수로 나누고 이후의 경우를 생각해 보자 import java.util.Scanner; public class last1 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); int count = 0; while (n != 1) { if (n % k == 0) { n /= k; count++; } else { n -= 1; count++; } } System.out.println(count); } } */