[JAVA] 이.코.테 (Greedy) - 1이 될 때까지

1이 될 때까지

문제

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

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

1. N에서 1을 뺀다.
2. N을 K로 나눈다.

N이 1이 될 때 까지 1번 혹은 2번의 과정을 수행해야하는 최소 횟수를 구하는 프로그램을 작성

입력

첫째 줄에 N(2<= N <= 100000)과 K(2 <= K <= 100000)가 공백으로 구분되며 각각 자연수로 주어짐

이때, 입력으로 주어지는 N은 항상 K보다 크거나 같음

출력

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

입력 예시
3 3
3 1 2
4 1 4
2 2 2

출력 예시
2

 

 

 

풀이

public class GoToOne {

	public static int one(int n, int k) {
		int count = 0; /// 횟수
		while (n > 1) {
			if (n % k == 0) {
				count++;
				n /= k;
			} else {
				count++;
				n-=1;

			}
		}
		
		
		return count;
	}

	public static void main(String[] args) {
		System.out.println(one(25, 5));
	}
}

아이디어 : 3분만에 푼 문제.,,, n에 -1을 하는 것보다 k를 나누는 것이 더 빠르게 1이 될 수 있다는 것을 생각하면서

              최대한 많이 나누기를 수행하였습니다. 

             나누어 떨어지지 않으면 -1, 나누어 떨어지면 나누어서 숫자를 줄여 나갔습니다.