그리디 - 1이 될때까지

문제

---

어떠한 수 N이 1이 될 때 까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다.
단, 두번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.
1. N에서 1을 뺀다.
2. N을 K로 나눈다.

예를 들어 N이 17, K가 4라고 가정하자. 이때 1번의 과정을 한 번 수행하면 N은 16이 된다.
이후에 2번의 과정을 두 번 수행하면 N은 1이 된다. 결과적으로 이경우 전체과정을 실행한 횟수는 3이된다. 이는 N을 1로 만드는 최소 횟수이다.
N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야하는 최소 횟수를 구하는 프로그램을 작성하시오

 

 

 

문제해결

---

1) 내 풀이

public static int hello(int n, int k) {
	int result = n;
	int cnt = 0;
	while(result!=1) {
		if(result%k!=0) {
			System.out.println("마이너스연산+1");
			result--;
			cnt++;
		} else {
			System.out.println("나누기연산+1");
			result /= k;
			cnt++;
		}
	}
	return cnt;
}

public static void main(String[] args) {
	int n = 25;
	int k = 3;
	System.out.println(hello(n, k));
}

결과: 6

 

 

2) 정답

public static int hello2(int n, int k) {
	int cnt = 0;
	
	while(true) {
		//n이 k로 나누어 떨어지는 수가 될때까지 빼기
		int target = (n/k)*k; // 25/3*3 = 24 -> 한번에 나누어 떨어지는 수 찾음
		cnt += (n - target); // 25 - 24 = 1 -> 마이너스 횟수는 1
		n = target; //n을 k로 나누어 떨어지는 수로 바꿔줌
		
		//n이 k보다 작을때(더이상 나눌수 없을때) 반복문 종료
		if(n<k) break;
		
		//k로 나누기
		cnt++;
		n /= k;
	}
	
	//마지막으로 남은수에 1씩 마이너스 연산
	cnt += (n-1);
	return cnt;
}

public static void main(String[] args) {
	int n = 25;
	int k = 3;
	System.out.println(hello2(n, k));
}

결과: 6

 

public static int hello2(int n, int k) {
	int cnt = 0;
	
	while(!(n<k)) { //n이 k보다 작은지 체크
   		
		//n이 k로 나누어 떨어지는 수가 될때까지 빼기
		int target = (n/k)*k; // 25/3*3 = 24 -> 한번에 나누어 떨어지는 수 찾음
		cnt += (n - target); // 25 - 24 = 1 -> 마이너스 횟수는 1
		n = target; //n을 k로 나누어 떨어지는 수로 바꿔줌
		
		//k로 나누기
		cnt++;
		n /= k;
	}
	
	//마지막으로 1이 될때까지 마이너스 연산
	cnt += (n-1);
	return cnt;
}

public static void main(String[] args) {
	int n = 17;
	int k = 4;
	System.out.println(hello2(n, k));
}

결과: 6

- 반복문 처음 시작할때 n이 k보다 작은지 검사(작을경우 마이너스 연산만 가능) 후 반복문 빠져나와서 1이될때까지 마이너스 연산한 횟수를 cnt에 집어넣음 이렇게 작성하는게 이해가 더 쉬움

 

해설

---

N은 양의 정수이기때문에 마이너스만으로도 언젠가는 1이될수 있음
하지만 마이너스보다는 나누기가 훨씬 더 빠르게 감소 가능, 그렇기에 가능하면 최대한 많이 나누는 작업이 최적의 해를 보장함

 

정답 코드에선 반복문 횟수를 줄이기 위한 스킬을 사용함

내가한건 반복분 한번 돌때마다 n을 체크해야됨(n이 클수록 반복횟수가 많아짐)
밑에처럼 하면 반복문 한번마다 n이 k로 나눠지는 연산을 수행해게됨
반복문 도는 횟수가 확 줄어들고 시간복잡도가 log 시간복잡도가됨