'알고리즘' 카테고리의 다른 글
| [BS] 백준 2792 보석 상자 (0) | 2018.04.29 |
|---|---|
| [BS] 백준 1477 휴게소 세우기 (0) | 2018.04.29 |
| [BS] 백준 2343 기타레슨 (0) | 2018.04.29 |
| [BF] 완전탐색 1018 체스판 다시 칠하기 (0) | 2018.04.29 |
| [BF] 백준 2775 부녀회장이 될 테야 (0) | 2018.04.29 |
[BS] 백준 6236 용돈 관리
2018. 4. 29. 00:45
푸는데 3시간 걸렸다.
문제를 잘못읽어서
제대로 읽고 20분 정도만에 fail 코드를 작성했는데 도저히
정확히 M번을 맞추기 위해서 남은 금액이 그날 사용할 금액보다 많더라도 남은 금액은 통장에 집어넣고 다시 K원을 인출할 수 있다.
이 경우를 처리할 방법을 모르겠었다.
좀 더 보니까 알겠다 저 fail 코드에 제일 아래에 쓴 코드 로 바꾸면 된다. 바보다 위는 고려안해도 되네
이 분의 코드는 저런 걸 다르게 언더플로우 걱정없이 할 수 있게 쓰는 코드라고 배울 수 있을 것 같다.
#include <iostream>
#include <algorithm>
#include <limits.h>
using namespace std;
typedef int ll;
ll tb1[100001];
int n, m;
// ll go(ll nn){ fail
// 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;
// }
// }
// 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;
}
// 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;
// }