알고리즘 분류
: 이분탐색
잘못 생각해서 접근했음.
1) 레코드 무게보다 작거나 같은 값일 경우에 담을 수 있음.
-> sum > mid 일 경우에 카운팅을 해야함!
왜냐하면 이제 새로운 레코드 기기에 담아야 하기 때문임.
2) 레코드 시작 갯수는 0이 아니라 1부터 시작해야 함.
왜냐하면? 레코드 1부터 담아야 하므로
: 이렇게 하더라도 58퍼센트에서 틀림.
아예 생각을 못한 부분.
mid 값이 컨테이너에 있는 것보다 작으면 false해야 함.
왜냐하면, 문제에서 모든 강의를 담아야 한다고 했기 때문임.
최종 코드
#include <iostream>
#include <vector>
using namespace std;
#include <algorithm>
int n, m;
bool binarySearch(vector<int>&v , int value)
{
int cnt = 1;
int ssum = 0;
for (int i = 0; i < v.size(); ++i)
{
// 왜틀렸을까?
// 여기 안하면,,, 58퍼센트에서 틀림.
if (v[i] > value)
return 0;
ssum += v[i];
if (ssum > value)
{
++cnt;
ssum = v[i];
}
}
return cnt <= m;
}
int main()
{
cin >> n >> m;
int sum = 0;
vector<int>v(n);
for (int i = 0; i < n; ++i)
{
cin >> v[i];
sum += v[i];
}
int res = 111111111;
int start = 1;
int end = sum;
while (start <= end)
{
int mid = (start + end) / 2;
if (binarySearch(v, mid))
{
end = mid - 1;
res = mid;
}
// 카운팅이 m보다 넘어서다는 의미.
else
{
start = mid + 1;
}
}
cout << res;
}
첫번째 코드
: 문제점. : 종료가 안됨.
- int를 반환하면서 갯수 확인하는 방식으로 함.
#include <iostream>
#include <vector>
using namespace std;
#include <algorithm>
int n, m;
int binarySearch(vector<int>&v , int value)
{
int cnt = 0;
int ssum = 0;
for (int i = 0; i < v.size(); ++i)
{
ssum += v[i];
if (ssum >= value)
{
++cnt;
ssum = v[i];
}
}
return cnt;
}
//
// 3일 경우
// 1 2
// 3
// 4 엄청 넘어감..
// 16 일 경우 : 1 2 3 4 5 : 15
// 6 7 : 13
// 8 9 : 17
// 24 일 경우 :
// 1 2 3 4 5 6 : 21
// 7 8 9
// => 2개밖에 못 담음.
// 1 : 50
int main()
{
// 10만 * 10만
cin >> n >> m;
// 정렬 하면 안됨.
// 모든 원소를 m개의 블루레이에 담아야 함.
// 이때의 최소값.
// 1 ~ 45
// 23
// 이진탐색으로 외부에 인자 1 ~ 45 값 넘겨 가면서
// 이진탐색 함수에서 확인을 하자.
// 21 일 때
// 1 2 3 4 5 6
// 7 8
// 9 -> 3개 이므로
// 줄여볼까?
// 45일때는
// 1개의 블루 레이에 모두 담을 수 있으니까
// 2개의 블루레이가 남음.
// cnt > 계산한 값.
// 이때는 end값을 mid - 1로 설정함.
// 2일 경우에는
// 1
// 2
// 3부터는 못담음. 즉 cnt:3보다 작으로므로 이때는 올리자.
int sum = 0;
vector<int>v(n);
for (int i = 0; i < n; ++i)
{
cin >> v[i];
sum += v[i];
}
int res = 111111111;
int start = 1;
int end = sum;
while (start <= sum)
{
int mid = (start + end) / 2;
// true일 경우.
int num = binarySearch(v, mid);
if (num == m)
{
//최소값 찾기
res = min(mid, res);
//cout << res << endl;
}
else if (num > m)
{
start = mid + 1;
//cout << "start" << endl;
}
else if(num < m)
{
end = mid - 1;
//cout << "end" << endl;
}
}
cout << res;
}
2번째 코드
- 내 생각에는 mid 값보다 크거나 같을때 카운팅 하는 방식으로 했음.
초기화를 0으로 잡아놓고, 했는데, 값이 틀림.
-> res 값이 16이 나옴.
왜냐 하면 내가 만든 함수문에서는 16이 통과과 되기 때문임.
-> 16이 통과되면 안됨.
내가 만든 코드에서 조금만 수정을 하면됨.
잘못된 부분
1) 비교시 >=
2) 레코드 카운팅의 초기값.
#include <iostream>
#include <vector>
using namespace std;
#include <algorithm>
int n, m;
bool binarySearch(vector<int>&v , int value)
{
int cnt = 0;
int ssum = 0;
for (int i = 0; i < v.size(); ++i)
{
ssum += v[i];
// 생각을 해보면..
// 1 2 3 4 5 6 7 8에서 17이라고 하면
// 1 2 3 4 5
// 6 7
// 8 에서 끝나므로.
if (ssum >= value)
{
++cnt;
ssum = v[i];
}
}
//if (ssum != 0) ++cnt;
return cnt <= m;
// 불로 처리하면 17로 true에 속하게 하고 증가시키자.
}
//
// 3일 경우
// 1 2
// 3
// 4 엄청 넘어감..
// 16 일 경우 : 1 2 3 4 5 : 15
// 6 7 : 13
// 8 9 : 17
// 24 일 경우 :
// 1 2 3 4 5 6 : 21
// 7 8 9
// => 2개밖에 못 담음.
// 1 : 50
int main()
{
// 10만 * 10만
cin >> n >> m;
// 정렬 하면 안됨.
// 모든 원소를 m개의 블루레이에 담아야 함.
// 이때의 최소값.
// 1 ~ 45
// 23
// 이진탐색으로 외부에 인자 1 ~ 45 값 넘겨 가면서
// 이진탐색 함수에서 확인을 하자.
// 21 일 때
// 1 2 3 4 5 6
// 7 8
// 9 -> 3개 이므로
// 줄여볼까?
// 45일때는
// 1개의 블루 레이에 모두 담을 수 있으니까
// 2개의 블루레이가 남음.
// cnt > 계산한 값.
// 이때는 end값을 mid - 1로 설정함.
// 2일 경우에는
// 1
// 2
// 3부터는 못담음. 즉 cnt:3보다 작으로므로 이때는 올리자.
int sum = 0;
vector<int>v(n);
for (int i = 0; i < n; ++i)
{
cin >> v[i];
sum += v[i];
}
int res = 111111111;
int start = 1;
int end = sum;
while (start <= end)
{
int mid = (start + end) / 2;
//bool temp = binarySearch(v, mid);
// true일 경우. 증가해야 함.
if (binarySearch(v, mid))
{
end = mid - 1;
res = mid;
//cout << "증가" << endl;
cout << res << endl;
}
// 카운팅이 m보다 넘어서다는 의미.
else
{
start = mid + 1;
//cout << "감소" << endl;
}
}
cout << res;
}
🔥🔥🔥