[BAEKJOON] 2613번 숫자구슬

https://www.acmicpc.net/problem/2613

2613번: 숫자구슬

• 구슬 N개를 그룹 M개로 나눈다.
• 각 그룹은 무조건 구슬이 1개이상이다.
• 모든 경우의 그룹을 나눴을때, 그룹의 최대값이 나올 수 있는 경우의 수 중 최소일때를 찾는다.

접근 방법이 도저히 떠오르지 않았다. 각 경우의 수를 모두 구해야하는 완탐으로 접근해야 하나,,?

N이 늘어날수록 어마무시하게 시간복잡도가 높아질게 뻔히 보이므로 알고리즘적으로 접근방법을 찾아야만 한다,,, 진짜 모르겠다

멍 때리고 1시간 정도 문제만 쳐다보니 번뜩 생각이 든 것이 수학적으로 접근하는 것이 아니라, 그냥 딱 눈으로 봤을때, 어떤 모양에서 최소값이 나올 수 있을까,,?

최대한 각 그룹의 값이 비슷해야 값이 한쪽으로 쏠려서 최대값과 최솟값의 편차가 작아진다. 

각 그룹의 값을 가장 공평하게 분배해주는 경우의 수가 바로 정답!!

 

이것을 구현할 방법은?

2024.03.14 - [Algorithm/Binary Search] - [BAEKJOON] 6236번 용돈 관리

[BAEKJOON] 6236번 용돈 관리

이전 매개변수탐색 문제가 바로 떠올랐다. 가장 공평하게 분배했을때의 최대값을 기준으로 참, 거짓인 이분적으로 구분할 수 있으므로 이 방법으로 접근해봤다.

???? 왜 틀렸지 진짜 맞는 것 같은데 ㅠㅠ

실행창에서는 올바른 결과가 나옴

문제를 한번 더 꼼꼼히 읽어 봤다. 

물론 나같은 경우에는 정답으로 right값이 나오도록 이분탐색을 구현했는데 이부분도 다시한번 봤다.

while (left + 1 < right) {
		//mid를 공평하게 배분했을때의 최댓값으로 둠
		int mid = (left + right) / 2;
		if (check(mid)) left = mid ;
		else right = mid;
	}

이 부분이 문제였다,,, 3시간 정도 삽질하면서 직접 알아보니 

while (left <= right) {
	//mid를 공평하게 배분했을때의 최댓값으로 둠
	int mid = (left + right) / 2;
   	 if (check(mid)) left = mid + 1;
	else right = mid - 1;
	}

 

????????

1. whlie문 안에서의 조건
2. left, right의 값 +,- 1

이게 무슨 의미가 있어서 틀리고 맞는 건지 생각해봤는데, 

 

 

 

 

이런 모양으로 결과가 나온다는 것이다. 그러니까 이때까지 계속해서 틀린 코드 부분은 주어진 예제 코드에서는 운이 좋아서 맞았지만, 실제로는 right를 답으로 하는 것이 아니라, 최솟값을 구하는 것으로 left를 답으로 해야 어떤 상황에서도 답이되는 것이었다,,!

 그러므로 while조건에서 left와 right가 겹쳐도 되는 부분을 만들어 줘서 이분탐색에서 F부분에서 T부분으로 넘어 가는 순간이 조건을 만족하면서 가장 최소인 순간이기 때문에 left<=right가 되어야한다.