풀이전략

• 왜 이분탐색이냐?
  
  : n개 중에서 m개를 반드시 뽑아야 한다고 하는데, 그러면
  완탐으로 하게 되면? 10만 * 10만이 될 수 있음
  -> 결론 : logN의 비용을 낼 수 있는 기법으로 가야 함.

😁7퍼센트에서 틀림.

: 나의 프로세스에 문제가 있음.
변경하려고 시도해야 함.

• 출력문을 통해서 체크함수에서 뭐가 잘못됬는지 확인함.
  
  
  -> 951일때는 총 3번 꺼내야 함. 프로세스가 잘못됨.

😁주의할 부분 _ 2프로 부족함.

1.반환되는 최대값 설정.

: 반환되는 최대값은 하루에 사용되는 모든 금액의 합으로 해야 함.
// 987654321로 하면 틀림.

• 왜 이렇게 설정해야 하는지?

  -> 아무생각없이 작성했는데, 상식적으로 생각하면, 가지고 있는 모든
  돈의 최대값은 합산이므로, 합산값으로 설정해야 함.

---

이분탐색 문제

: left와 right 값 설정을 잘해야함!!

• 주의할점.
  : 문제대로 풀어나가서 check 함수를 == 으로 반환하게 되면,
  계속해서 Min값이 커지는 문제가 발생하게 되므로,
  부등호를 사용해야 함.

• 생각해내지 못한 부분.

1) 도대체 돈은 얼마정도가 있어야 할 것인가?
돈의 범위를 이분탐색으로 접근할 것인데, 얼만큼의 돈을 설정할지를
생각을 못함.
-> 입력으로 주어지는 돈들의 모든 합으로 처리하자.

2) check 함수에서 반환하는 부분에 대해서
돈이 모잘라서 초기화를 했는데도, mid값이 < v[i] 일 경우,
이것은 절대 계산 자체가 안됨. 계속해서 , 초기화를 할 것임.

첫번째 코드

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <algorithm>

int n, m;

bool check(vector<int>&v , int target)
{
	int cnt = 1;
	int num = target;

	for (int i = 0; i < v.size(); ++i)
	{
		if (num >= v[i])
		{
			num -= v[i];
		}
		// 모자랄 경우, 초기화해야 함.
		else 
		{			
			num = target;
			++cnt;

			if (v[i] > target)
				return false;
			num -= v[i];
		}
	}

	// == 을 하게 되면, 무조건 mid 값이 커짐.
	return m >= cnt;
}


int main() 
{
	// n번을 입력해서, 하루마다 사용해야 하는 금액
	// 2번째 입력값 : m은 정확히 교체되어야 하는 금액임. 
	cin >> n >> m;

	vector<int>v(n);
	int sum = 0;
	for (int i = 0; i < n; ++i)
	{
		cin >> v[i];
		sum += v[i];
	}

	// 왜 이분 탐색이냐? 
	// 타겟팅 값을 통해서 모든 n을 순차 탐색을 할것임. 
	// 그리고, 반드시 m의 횟수만큼의 돈을 초기화해야 함.
	// m은 여기서 1만임. 
	// 그러면.. 10만번 순차 탐색을 하면서, 1만 번 탐색? 
	// 이분탐색으로 접근하자.

	int Max = *max_element(v.begin(), v.end());
	int Min = *min_element(v.begin(), v.end());
	int result = Max;

	while(Min <= Max)
	{
		int mid = (Max + Min) / 2;

		if (check(v, mid))
		{
			//result = min(mid, result);
			result = mid;
			Max = mid - 1;
			
		}
		//false 가 나타내는 것은,,, 
		// m번을 초과했다는 것을 의미 -> start  = mid + 1
		else
		{
			Min = mid + 1;
		}
	}

	cout << result;
}

내 생각에는 어차피 입력값 들 중에서 찾는 거라고 생각해서

이렇게 설정한 후, mid 값을 탐색 했는데,
백준에서 틀리대... --;;

• max 와 min 을 처음에 설정을 잘해야 함.
  왜 그럼???!
  일단 조거에서 금액에 대한 조건을 주었기 때문에
  min = 1 로 설정해야 함.
  

max에 대해서 만약에

이렇게 되어 있는데 , m이 1 이라고 한다면??
내 생각대로 원소의 최대값 500가지고는 해결할 수 없음!
최대한 큰수로 설정을 해야함.
그게 도대체 얼마인데? 합으로 처리해야 함...

최종 코드

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <algorithm>

int n, m;

bool check(vector<int>&v , int target)
{
	int cnt = 1;
	int num = target;

	for (int i = 0; i < v.size(); ++i)
	{
		if (num >= v[i])
		{
			num -= v[i];
		}
		// 모자랄 경우, 초기화해야 함.
		else 
		{			
			num = target;
			++cnt;

			if (v[i] > target)
				return false;
			num -= v[i];
		}
	}

	// == 을 하게 되면, 무조건 mid 값이 커짐.
	return m >= cnt;
}


int main() 
{
	// n번을 입력해서, 하루마다 사용해야 하는 금액
	// 2번째 입력값 : m은 정확히 교체되어야 하는 금액임. 
	cin >> n >> m;

	vector<int>v(n);
	int sum = 0;
	for (int i = 0; i < n; ++i)
	{
		cin >> v[i];
		sum += v[i];
	}

	// 왜 이분 탐색이냐? 
	// 타겟팅 값을 통해서 모든 n을 순차 탐색을 할것임. 
	// 그리고, 반드시 m의 횟수만큼의 돈을 초기화해야 함.
	// m은 여기서 1만임. 
	// 그러면.. 10만번 순차 탐색을 하면서, 1만 번 탐색? 
	// 이분탐색으로 접근하자.

	int Max = sum;
	int Min = 1;
	int result = Max;

	while(Min <= Max)
	{
		int mid = (Max + Min) / 2;

		if (check(v, mid))
		{
			//result = min(mid, result);
			result = mid;
			Max = mid - 1;
			
		}
		//false 가 나타내는 것은,,, 
		// m번을 초과했다는 것을 의미 -> start  = mid + 1
		else
		{
			Min = mid + 1;
		}
	}

	cout << result;
}

젠장!