컴공 일기260
게시글 주소: https://io.orbi.kr/00070877031
https://www.acmicpc.net/problem/6236
백준 6236번 (S1) 솔루션 by c++
생각보다 이분 탐색 로직은 쉬운 듯 한데, 디테일에서 에러를 많이 냈던 문제입니다.
특히 high의 범위가 금액의 MAX가 아닌 금액들의 총합으로 잡아야 한다는 게…
생각없이 코딩했을 때 놓칠 수 있는 부분이랄까요…
#include <iostream>
using namespace std;
int day_money[100002];
int N, M; //N: 일 수, M: 인출 횟수
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> M;
int sum = 0;
for(int i=0; i<N; i++)
{
cin >> day_money[i];
sum += day_money[i];
}
int low = 1;
int high = sum;
while(low<=high)
{
int mid = (low + high) / 2;
int cnt = 1;
bool flag = true;
int current = mid;
for(int i=0; i<N; i++)
{
if(day_money[i] > mid)
{
flag = false;
break;
}
if(current < money[i])
{
current = mid;
cnt++;
}
current -= moeny[i];
}
if(flag == false || cnt > M)
{
low = mid + 1;
}
else
{
result = mid;
high = mid - 1;
}
}
cout << result << endl;
}
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
학기중에는 바빠서 독서를 많이 못했네요..
-
화산귀환 웹툰보다는 전개가 시원시원하네 근데 전독시도 실사화 나오면 바로 따라잡히는거 아닌가
-
친구가 본인은 야행성이라고 오전 11시에 일어나서 새벽3시에 자더니재수 폭망함 내가...
-
아예모다겟음
-
22 국어 수학 진짜 불로 나온거 잘보고 오히려 탐구를 망쳐버려서 서울대 그대로...
-
첫알바 어디가 ㄱㅊ? 15
돈이 부족하거나 알바해야만 하는 당위성이 있는 건 아닌데 더 늦기전에 경험해보는...
-
확통 재밌는데 10
진입장벽도 거의 없고 개념이랄 것도 없고 발문 따라 케이스분류만 하면 되어서...
-
2만덕 드림 나군 밖에 안 될 거 같아서 나군 기준으로 합니다 최초합 ~ 예비...
-
비행기랑 빙고ㅆㅅㅌㅊ
-
남자가 여자에게 귀엽다~ 하는것도 어느정도 외모가 기준선을 넘어야 하는거겠죠? 막 이쁜건 아니여도
-
"내년에도 화1 할래?"
-
8시 기상 밥 먹고 9시까지 독서실 가기 9~12시 국어 점심 30분+10분동안...
-
건대
-
체력은 그냥 종잇장급입니다 요즘 공부한답시고 1시반에 자서 8시에 일어나는중인데 좀...
-
의대합격보다 진지하게 어려운듯 국가유공자혈통도있어야되잖아
-
68 95 99.7 10
보통 신뢰구간 구할 때는 a=0.05를 쓰죠 점공에서는 예측 구간이라고도 합니다
-
얼버기 7
7시에 자서 지금 일어났음요 내일 긴 여정을 떠나야 하는데 큰일났다!!
-
없어서 공부했다고.
-
난 자꾸 돌아보겠죠 그곳엔 아직도 그대가 있어서 그래서 아픈가봐요 한 번쯤 꼭 한...
-
おやすみなさい 5
오부이 잘자
parametric search인가
오 맞아요
매개변수 탐색이 맞왜틀 잘당함 디테일때문에
진짜 그 디테일 놓치면 몇 시간이고 고생하는 케이스가 많더라구요.. 참 겸손해지는 파트인 듯 합니다,,
열심히하세요 ㅎㅎ
요즘 제가 약한 dp문제들을 bottom up 방식으로 풀어보는 연습을 많이 하고 있는데 이런 주제도 있었군요 참고하겠습니다
dp… 화이팅입니다 :)