[이것이 취업을 위한 코딩테스트다] Ch.03 그리디 - 1이 될 때까지 (Java)

문제

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

두번째 연산은 N이 K로 나누어 떨어질 때만 선택 가능

 

1. N에서 1을 뺀다

2. N을 K로 나눈다

 

입력조건

N(2<=N<=100,000), K(2<=K<=100,000)가 공백으로 구분되어 각각 자연수로 주어짐. N은 항상 K보다 큼

 

출력조건

첫째 줄에 N이 1이 될 때까지 1번 혹은 2번 과정을 수행해야하는 횟수의 최솟값을 출력

풀이/후기

최대한 많이 나누기를 수행

코드

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) 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 cnt = 0;
		while (N > 1) {
			
			if (N % K == 0) {
				N /= K;
				cnt++;
			} else {
				N -= 1;
				cnt++;
			}
			
			if (N == 1) {
				break;
			}
			
		}
		
		System.out.println(cnt);
		
	}

}

Commit

https://github.com/allrightDJ0108/CodingTestStudy/commit/9f50af395b6a2bb0675f7c51107499eed86ac804