컴공 일기260
게시글 주소: https://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를 선물하세요.
-
결승전 아직도 하고 있네 1 0
-
꺄아악 0 0
끼요오오옥
-
경기 내용 생각하면 오히려 골이 넘 늦게 터진 것 같아요 9 1
슈팅 개수가 20 대 0 인데
-
아르헨멸망ㅋㅋㅋㅋ 1 1
스페인 우승 가자~
-
ㅅㅅㅅㅅㅅ 0 1
ㅅㅅㅅㅅㅅ
-
결국엔 페토가 이렇게 1 1
캬
-
축구의승리 0 1
-
!!!! 0 1
!!!!!!!!!!
-
아르헨 참교육 ㅅㅅㅅㅅㅅ 0 0
컷
-
캬캬 1 0
-
스페인 골 0 1
대박
-
낄낄낄 1 0
꼴좋다 ㅋㅋㅋㅋ
-
캬 2 0
ㅅㅅㅅㅅ
-
결승 경기기록이 좀 약빨았는디 0 0
이.이게모임.. 메갓이시여....................
-
스페인이 잘하네 10 2
뭔가뭔가 압도적인 느낌
-
아직두 결착이 안낫넹 아침먹구 뒹굴거리다가 문득 떠올라서 검색해봣단말이ㅣ디
-
자다가 일어났는데 가족들이 월드컵 결승전 보고 있길래 잠 깨서 보는중
-
이게왜 2 0
흠.......
-
매수완료 0 0
-
갑자기 레오나 궁 맞은 것 마냥 쓰러져서 연기하노 ㅋㅋ
-
이게왜 1 0
매수함???.?.????
-
니코윌리엄스가 골망을 흔들긴함
-
결승은 노잼이네요 4 0
네
-
아르헨티나 0
-
운동 가기전에 찍어가는 초식 사용중
-
카투사 기원 7+5일차 0 0
-
나학교가야된다고요 6 0
아니후반까지딱보고 한시간더자려고했는데 나아까한시간반밖에못잤어
-
심판 매수된줄 알고 파울 남발하고 있다는 나쁜말은 ㄴㄴ 7 3
ㄴㄴㄴㄴㄴ
-
아르헨티나 수준 ㅋㅋㅋㅋ 1 1
다리 담굴려고 축구하낰ㅋㅋㅋㅋ
-
스페인 프리킥 제발 끝내자 0 0
나 졸려
-
아르헨티나는 3 1
그냥 반칙왕인데
-
ㅈㄹㅋㅋ 0 1
교통사고를 내버려
-
연장도 30분이나되는데 0 0
안그래도 밀리고있었는데
-
(예정) 지금까지 구토해적단을 사랑해주셔서 감사합니다. 9 2
엔소가 기어코 사고를 쳐버리네요
-
뭐하냐 씨발 장애인아 2 1
생각이 없냐 레드감이네
-
쉣 ㅋㅋㅋㅋㅋ 1 1
퇴장 ㅋㅋ
-
얼버기 2 1
여신님 보고 화이팅 하세요
-
0대 0으로 갈려나 2 0
먼가먼가 아슬아슬한데 수비를 잘하네
-
구토국놈들 옐로만 몇개냐 7 1
이게축구여?
-
연장안가면 좋겠는데 0 0
졸림 시상식 이런거하면 몇분정도 보이려나 그래도 럼프 보고픈데
-
이건 뭐.. 얘네 입장에서는 승차로 끌고 가려는 전략 같은데 스페인은 슬슬 끝내려고...
-
왤케 다 정면으로가냐 2 0
내가 가서 좀 알려줘야되나?
-
바둑경기도 이것보단 재밌을듯 0 1
그냥 스페인이 이긴걸로 치고 경기끝내죠
-
이게 신기한게 2 1
막 뛰어다니는거같은데 대열이 유지되네 고등학교 축구는 공 주위에 15명씩 모여있는데
-
경기 요약좀
-
체급차가 심하게 나네 3 1
걍 편하게 봐야될듯
-
ㅇㅂㄱ 4 0
공부하자
-
ㅇㅂㄱ 1 0
오늘도 재미없는 기출을 풀겠군ㅏ아
-
거의 반코트인데? 8 4
텐백 수비 때문에 아직 골만 안 들어가네
-
야말이 07년생이라고? 2 1
그럼 같은 07년생인 나는 왜이런거지
parametric search인가
오 맞아요
매개변수 탐색이 맞왜틀 잘당함 디테일때문에
진짜 그 디테일 놓치면 몇 시간이고 고생하는 케이스가 많더라구요.. 참 겸손해지는 파트인 듯 합니다,,
열심히하세요 ㅎㅎ
요즘 제가 약한 dp문제들을 bottom up 방식으로 풀어보는 연습을 많이 하고 있는데 이런 주제도 있었군요 참고하겠습니다
dp… 화이팅입니다 :)