문제 링크입니다: https://www.acmicpc.net/problem/6236
전형적인 이분탐색 문제였습니다.
*주의할 점은, 인출하는 양이 하루 쓸 돈보다 적으면 안된다는 점입니다.
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX = 100000;
int N, M;
int cash[MAX];
bool func(int mid)
{
int num = 1;
int sum = mid;
for (int i = 0; i < N; i++)
{
//인출하는 양이 하루 쓸 돈보다 적으면 모순
if (mid < cash[i])
return false;
if (sum - cash[i] < 0)
{
sum = mid;
num++;
}
sum -= cash[i];
}
return M >= num;
}
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
int sum = 0;
for (int i = 0; i < N; i++)
{
cin >> cash[i];
sum += cash[i];
}
int low = 1, high = sum;
int result = 0;
while (low <= high)
{
int mid = (low + high) / 2;
if (func(mid))
{
result = mid;
high = mid - 1;
}
else
low = mid + 1;
}
cout << result << "\n";
return 0;
}
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
'알고리즘 > BOJ' 카테고리의 다른 글
백준 15732번 도토리 숨기기 (0) | 2019.02.04 |
---|---|
백준 5425번 자리합 (0) | 2019.02.04 |
백준 2343번 기타 레슨 (0) | 2019.02.04 |
백준 2022번 사다리 (0) | 2019.02.04 |
백준 2792번 보석 상자 (0) | 2019.02.04 |