'알고리즘' 카테고리의 다른 글
| [DC] 백준 2261 가장 가까운 두 점 (0) | 2018.04.29 |
|---|---|
| [DC] 백준 11729 하노이의 탑 이동순서 (0) | 2018.04.29 |
| [DC] 백준 11728 배열 합치기 (1) | 2018.04.29 |
| [DC] 백준 1780 종이의 개수 (0) | 2018.04.29 |
| [BS] 백준 2512 예산 (0) | 2018.04.29 |
[DC] 백준 6236 용돈관리
2018. 4. 29. 00:57
#include <iostream>
#include <algorithm>
#include <limits.h>
using namespace std;
typedef int ll;
ll tb1[100001];
int n, m;
ll go(ll nn) {
ll cnt = 1;
int account = nn;
for (int i = 0; i<n; ++i) {
if (account - tb1[i] >= 0) {
account -= tb1[i];
}
else {
cnt++;
account = nn - tb1[i];
}
}
return cnt;
}
// ll go(ll nn){
// ll cnt = 1;
// int account = 0;
// for(int i=0;i<n;++i){
// if(account + tb1[i] > nn){
// cnt++;
// account = tb1[i];
// }
// else{
// account += tb1[i];
// }
// }
// return cnt;
// }
int main(void) {
ll sum = 0, maxv = 0;
cin >> n >> m;
for (int i = 0; i<n; ++i) {
cin >> tb1[i];
maxv = max(maxv, tb1[i]);
}
ll left = maxv;
ll right = 1987654321; // large value
while (left <= right) {
ll mid = (left + right) / 2; // mid는 정한 가격
//cout << mid << endl;
int tempv = go(mid);
if (tempv > m) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
cout << left << endl;
return 0;
}