풀이 전략 : 241111 결론을 보자...

• 문제를 보고 어떻게 접근할지 엄두가 안난다.

: 일단은 n 아이들이 10의 9승이므로 logN의 시간복잡도의 알고리즘으로 해야겠다는 생각을 함.

아래의 문제의 예시에서 아이가 5명이고, 빨간보석 4개 , 파란보석 7개라고 했다. 어떻게 이분탐색으로 접근할지를 모르겄다...

어떻게

: 어쨋든 탐색을 하는 것이기 때문에 뭔가를 기준으로 잡을까???
대상을 정해야 한다!!

• 큰돌님은 질투심이 ~~ 일 때를 기준으로 해서 질투심으로 나누는 방식으로 진행한다.. 왜 그럴까?
  : 출력 내용은 질투심을 최소화하는 것이다. 그래서 질투심을 기준으로 해서 진행을 한다. 질투심이랑 가장 많은보석을 가지는 학생이 가지고 있는 보석의 개수 이다.

질투심으로 나누는 것은 가장 많은 보석으로 v[i] 를 나누는 것이다.

• 에이포 용지가 있다면 일단 그려보자.
  : 지금의 경우, 어떤 식으로 접근할지 예상이 안된다.

• 아래의 그림은 질투심이 4개인 경우인데, 이 때는 학생이 3명이므로 불가하다.
  

• 질투심이 3개일 때 5명의 아이들이 모두 보석을 가져갈 수 있다.
  

결론 241111

: 타겟 대상을 잡기가 굉장히 곤란하지만, 탐색 대상을 찾아야 한다.
지금의 경우는 결론적으로 질투심 아이들 중에서 가장 많은 보석을 가지고 있는 친구가 가진 보석이라는 것이다. 이분탐색을 하든 뭘 하든 궁극적으로는 보석을 가지고 있는 갯수가 최소한이 되어야 한다는 점이므로, 질투심을 대상으로 해야 한다.
탐색 대상이 찾기 어려운 이유는 질투심은 가장 많은 보석을 가져간 학생인데, 그럼 그 학생은 한명 또는 두명이 아닐까???????????? 라는 생각을 가지게 되면서 이거 어떻게 푸냐라는 생각을 하게 되었따...

---

최근 풀이 : 240210

: 문제를 보고, 어쨋든 사람의 수는 보석의 수보다 크거나 같음.
그래서 내가 생각한 것은 이렇다.

• 현재 사람의 수 7, 보석의 수 5개 이기 때문에 (보석 : 7 1 7 4 4)
  최대한 많은 사람들이 보석을 최대한 쪼개서 질투심을 낮춰야 하기 때문에
  저거를 내림차순으로 정렬 해서 가장 큰수에 많은 사람을 투여하려고 함.
  -> 그런데 이렇게 하면 복잡하고, 재귀를 돌리면서 다음인덱스를 생각해야 하기 때문에
  굉장히 복잡해짐.
  

• 예를 들면 사람아 15이고 나머지는 동일할 경우.
  7을 4명이 분배하고 , 7을 4명이 분배하고, 1을 한명만 ,
  4를 2명이 , 4를 2명이 이렇게 분배가 가능함..
  

  - -> 잘못된 접근 방법....

• 일단 나는 100000000 이기 때문에 logN의 방법으로 해야 겠다라는 생각을 함.

• 큰돌님은 여기서는 한사람이 가지는 보석의 갯수를 최소한으로 만들어야 하기 때문에
  질투심이 몇개 일때? 를 기준으로 잡고 진행해야 한다고 함.
  

• 어떻게 풀것인가?
  이분탐색을 이용 : 벡터의 max값을 right 값으로 하고, left 를 1로 한 후, mid 구함.
  mid 값으로 모든 원소의 밸류 나눠가면서 진행.. 카운팅....
  https://www.acmicpc.net/submit/2792/48013677

---

문제의 예시대로 풀면 틀림.

잘못된 접근 방법.

잘못된 프로세스

: 문제의 예시도로 풀었음. -> 틀림.

• 사람수 카운팅해서 비교하는 프로세스와, 최종적인 질투심 처리하는 부분을
  구분해야 된다는 생각을 해야함.
• 나머지가 존재할 경우, 나는 그 나머지를 한 사람에게 몰아주는 방식으로 했음. -> 사람수를 카운팅하는 것이 아니라.
  왜 이렇게 했냐면? 하나의 프로세스에서 질투심도 구하기 위해서 이렇게 함.

올바른 프로세스

: 문제의 예시대로 풀지 않음.

• 사람수 카운팅해서 비교하는 프로세스와, 질투심을 만약에 분리했다고 한다면?
  , 굳이 나머지 값을 이용해 질투심 처리하는 코드를 만들 필요가 없음.

• 그리고 생각을 해보면,
  7개의 보석을 보석 2개로 나눈다고 생각을 하면, 사람은 3명뿐 아니라,
  나머기 1개의 보석이 나오므로, 사람 한 명이 추가됨.

기준이 질투심이므로, 질투심이 되는 보석을 나누는 수를 기준으로 해서 진행하자.

-> 나눠서 나오는 수는 사람의 수 이고, 나머지가 나오면 ,
딱 한 사람에게 전달할 수 있는 것이다!
-> 질투심을 기준으로 해서 이분 탐색을 진행 하면. 잘못된 프로세스를
작성할 고민이 없엇음.

전략! 241024 최근 업데이트

1) logN으로 접근해야 겠다는 생각을 했기 때문에 이분탐색으로 진행해야 겠다.
2) 타겟 대상을 어떻게 잡을 것이냐? 가 관건이다.
: 여기서는 질투심을 최소가 되게 해야한다고 했기 때문에 질투심을 최소로 하자.

• 문제에서 오로지 한사람은 동일한 보석종류만 가져가야 한다고 했다.
  가) 보석을 2개씩 선택하면?

나 ) 보석을 3개씩 선택하면?

-> 이렇게 진행하면 되는데, 학생 중 보석을 갖지 못할수 있다고도 한다.
이를 유념해서 작성하면 된다.

개선할 점

1. 문제의 핵심으로 바로 풀수 있도록 하자.
2. 데이터 범위가 큰것을 확인했으면, 더도 말고 long long으로 선언하자.
3. 문제를 잘 읽어보자...

1번. 문제를 잘 읽어보자.

: 문제에서 보석을 받지 못한 사람이 있을 수 있다고 함.
그런데 나는 sum == n으로만 처리했음.
-> 잘못된 프로세스

• 그림
  

1) 사람 수를 구함.
2) 사람수와 n이 동일할 경우, 질투심 측정함.

• 그림
  : 7퍼센트에서 틀림.
  

2번. 데이터 범위가 어마어마하다 싶으면, 변수 처리를 long long으로 설정하자.

• 결론 : 현재 구하고자 하는 것은 질투심이므로, 질투심에 초점을 맞춰서
  코드 작업을 해보자.

---

이분탐색

: 어차피 반절씩 줄여나가면서 진행을 할 것이므로,
초기값 범위를 0 ~ max 값으로 설정해서 진행하자.

풀이

• 여러개의 보석의 수를 어떻게 나눠야 할지 고민을 했지만,
  이렇게 접근하지 말고, 최적의 해를 어떻게 찾아낼지가 중요함!

• n과 입력값이 10억이라서 이분탐색 해야 겠다 생각함.

결론 : 관건은 입력값이 너무 많고, 이를 logN의 비용으로 처리하면서
탐색을 해야 하므로, 이분탐색으로 풀어야 겠다는 사로를 해야 함.
이분 탐색이므로 처음에 설정한 start와 end값을 어떻게 잡을지에 대한
사고를 해야함.

내가 생각한 풀이가 의구심이 들때는 입력 예제를 통해 답이 나오는지를
생각하자.

이분 탐색으로 했을 때 가능한 이유는
5 2
7
4
로 생각을 해보면.
나눴을때의 값을 구하는 것이므로 최소값을 1로 두고, 최대값을 7로 두고
생각을 하자. 추가적으로 사람 수 5명을 맞춰야 함.
최소값을 4로 하게 되면, 안됨.

반례

: 일단 이분 탐색으로 하려고 했는데
4 25 사람 : 5
라고 하면 어떻게 할 건데?
6으로 나눠야
25 / 6 -> 4가 됨.
그럼
4 / 6 -> 0인데?
이 부분을 고려해야 함.

알아야 할 점.

: 문제의 흐름대로 작성해 나가려고 하면...

상자에 빨간 보석이 4개 (RRRR), 파란 보석이 7개 (BBBBBBB) 있었고, 이 보석을 5명의 아이들에게 나누어 주는 경우를 생각해보자. RR, RR, BB, BB, BBB로 보석을 나누어주면 질투심은 3이 되고, 이 값보다 작게 나누어 줄 수 없다.

• 나누면 어떻게 될까?
  사람 5 명
  나는 1 ~ 4 까지로 나누려고 함.
  1로 진행하면? -> 11명
  2로 진행하면 ? -> 빨 2명, 파 3명 , 파란색 1개 남음.
  3으로 진행하면 ? -> 빨 1명, (빨간색 1개 남음), 파 2명 (파란색 1개 나음)
  4로 진행하면? -> 빨 1명, 파 1명(파란색 3개 남음)
  -> 근데 출력은 3이 최소값임.

풀면서 느낀점.

: 내가 진행하려 했던 코드는 5명과 빨, 파 인원수를 비교하려고 했는데,
이렇게 하더라도 질투심의 최소값을 구할 수 없음
그리고 rr, rr, bb, bb, bbb 라고 하는데,
그러면 답은 2가 아닐까? 생각되는데 ,
코드와 문제에서 처리한 것이 일치가 안됨....

• 3이라고 한다면?
  rrr, r, bbb, bbb, b 이다.
• 나누면 어떻게 될까? 에서 3으로 진행하면? 을 보면?
  3으로 진행하면 ? -> 빨 1명, (빨간색 1개 남음), 파 2명 (파란색 1개 나음)

나머지가 0이 아닐 경우도 사람을 카운팅 할까? 에 대해 생각을 해볼수 있음.

반드시 문제의 설명대로 풀려고 하지 말아야 함!

• 예제 입력 을 보자...
  

나머지가 0이 아닐 경우에 카운팅을 한다고 한다면?
예제 1번과 예제 2번에서 확인해보자.
예제 1 번 : 7, 4 -> 3 으로 나눠 ? 2(몫) + 1(나머지) 카운팅 , 1(몫) + 1(나머지) -> 5명의 사람이 나옴.
예제 2번 : 7, 1, 7, 4 , 4 를 4로 나눠?
1(몫) + 1(나머지, 3이지만, 1 카운팅) , 0(몫), 1 카운팅 ~~
-> 7명의 사람이 나옴.

코드

#include <iostream>
#include <vector>
using namespace std;
#include <algorithm>
long long n, m;
bool check(vector<long long>&v , long long mid)
{
	// 8명의 아이들이라면? 
	int cnt = 0;
	for (int i = 0; i < v.size(); ++i)
	{
		cnt += v[i] / mid;
		if (v[i] % mid) ++cnt;
	}

	// 입력으로 들어오는 사람의 수와
	// 계산 후의 수를 비교해야 할듯? 
	return n >= cnt;
}


int main()
{
	
	cin >> n >> m;

	vector<long long>v(m);
	for (int i = 0; i < m; ++i)
	{
		cin >> v[i];
	}
	// 한 학생은 오로지 하나의 색상의 보석만
	// 가져갈 수 있음. 
	// 보석 중에서 가장 작은 것이.
	// 나눌수 있는 가장 높은 수임.
	// 1 ~ 4 

	// for문으로 1 ~ 4까지 돌리기에는 
	// n의 수가 십억, m 은 30만이므로.
	// 효율적으로 접근해야 함. 

	// n이 십억이고,
	// 입력값이 1 ~ 십억인데, 
	// 만약에 1억이 최소값이 라면.
	// 1 ~ 1억까지 , 십억명의 사람을 돌리면서 처리하기에는 옳지 못함.

	//== 
	// 처리
	// 보석a : 4 개,  보석 b : 7개
	// 나눌 수량 : 1 ~ 4 
	// 5명의 사람으로 나눔

	long long r = *max_element(v.begin(), v.end());
	long long max = 999999999;
	long long l = 1;
	 
	while (l <= r)
	{
		long long mid = (l + r) / 2;

		// 사람 인원수가 일치한다면
		if (check(v, mid))
		{
			max = min(max, mid);
			r = mid - 1;
		}
		// 사람 수가 더 적다면
		else
		{
			l = mid + 1;
		}

	}

	cout << max << endl;
}