컴공 일기260
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를 선물하세요.
-
추ㅐㄹ비 12
40도양주마시거잔득취해버렷
-
오늘도 조용하네 5
내 일기장이 되었구나
-
생각보다 잘해주시네.. 만족스러워요
-
첫알바 어디가 ㄱㅊ? 15
돈이 부족하거나 알바해야만 하는 당위성이 있는 건 아닌데 더 늦기전에 경험해보는...
-
수분감 0
수분감은 왜 저평가받는거임? 뉴런들을사람은 수분감듣는게 더 효율적인게맞지않음?
-
쿵푸허슬 1
개재밌네 몇번을 다시봐도 재밌군
-
뭐가 더 쉽나요?
-
하루에 1gb 정도면 충분하겠죠?
-
그냥 순수 ㅂㅅ짓으로 환급 못받아서 날리는데 어캄
-
성형하고싶다 1
진심 눈코입 얼굴형 싹다뒤엎고싶음
-
현실에서 고등학교나 대학교에서 동성친구끼리 니정도면 ㅎㅌㅊ임 개빻음 이러고...
-
보상 받을지말지 때문인게 큰듯 그냥 1등급 나오는애들한테 공부하는건 어느정도 성적이...
-
빰빰빠바빰 2
즐거운 고연전 날에
-
나중에 막 코 들리면 어캄
-
제가 지금 모집인원의 딱 50%인 예비 번호를 받았는데 과거 3개년 모두 충원율이...
-
사람마다 최대치가 다르고(재능) 그 속에서 이제 노력으로 정해지는 듯 A는 태어났을...
-
옛날에 만든 거라 불연속 함수 적분 교과과정 안 들어가는 거 모르고 만듦.<--...
-
집에서 가장 가까운 관독이 여긴데(대중교통 20) 관리 빡센가요
-
메가패스 성적입력안해서 돈 환급 못받는 미친놈이접니다 어머니께서 알바비로 메꾸라네요
-
오늘 학생 둘이 저녁시간때 와서 중대 합격한거 축하한다 해서 사실 성대도 이미 합격...
-
시대 장학금 4
백분위 합 282 인데 이정도면 장학금 한푼도 못받음?
-
자금이좀딸리지만 걍살까..
-
흠냐 그리고 단원별 융합 문제는 어디로 분류해야할지 난감스함
-
-
https://xurl.es/4stnb
-
대학백과 여기에 2
답변 남겨보셨나요? 대학 다녀보신 분들
-
오히려 커뮤가 높게 쳐주는듯 ㅋㅋ 커뮤 3수 중경외시면 그래도 괜찮다고 봐요<...
-
배가너무아프긔 집까지 15분인데 그냥텐레포트하고싶다
-
-
면허땄다 12
만세
-
( 정부의 비과학적 졸속 의대증원 2000명증원이 증발시킨 건보 재정 2.9조원 ) 3
보건복지부 장관 조규홍 보건복지부 차관 박민수 교육부 장관 이주호 ... 등에게...
-
특정당할 일은 절대 있을 수 없음.
-
저메추 부탁함뇨잇.
-
외대ㅜ경제 0
빵 기원.. 쩝 표본상으로는 나름 빠질 인원 많아보였는데
-
가형은 무섭다 7
18 가형 1점차인데 백분위가 ㄷㄷ...
-
작수 강준호 커리타고 19,20 못 풀고 45점 나왔습니다. 이번에 김준...
-
피방오르비중인데 5
뒤에서 자꾸 힐끗대네 특정완료인가..
-
시립대랑 외대 경영 둘 다 붙을거같은데 어디 가는게 나을까요 아버지 회사에서...
-
탈릅해야겟다 3
왜 급할때 글 쓰면 맨날 답변 안 달림? 나 서운해...
-
노예비떨 ㅋㅋㅋㅋㅋㅋㅋ ㅜㅜㅜㅜ
-
끌끌..
-
뉴카멘 지리네이
-
탈릅?
-
뭔가 있어보이게 포장하기 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
-
케바케라곤하지만 난 항상 운이 없기에 개쓰레기자대로 갈거같음 새삼 뭔가 이리저리...
-
디시 빡갤도 나 하는데 거기선 익명인데다 지나치게 자유로운 곳이라 아무 뻘글이나...
-
이마에 이슬이 간절히
-
옯만추는 어케하는거임 16
나 98년생인데 아저씨랑 비밀친구하자 으흐흐
-
예비법조인분들 파이팅
-
왜 그렇게까지 하는거야 도대체
parametric search인가
오 맞아요
매개변수 탐색이 맞왜틀 잘당함 디테일때문에
진짜 그 디테일 놓치면 몇 시간이고 고생하는 케이스가 많더라구요.. 참 겸손해지는 파트인 듯 합니다,,
열심히하세요 ㅎㅎ
요즘 제가 약한 dp문제들을 bottom up 방식으로 풀어보는 연습을 많이 하고 있는데 이런 주제도 있었군요 참고하겠습니다
dp… 화이팅입니다 :)