컴공 일기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를 선물하세요.
-
쓸글이없어요
-
올해 수능 응시하고 인서울 의대 성적이 나왔는데, 메디컬은 선호하지 않아...
-
진짜 키스가 좋음? 16
침섞이는게 더러운데
-
너무 안정인가 3
학교를 높이면 추합도 어려워짐.. 과를 조금 높여볼까요ㅋㅋㅋㅋ 이렇게 쓰는 사람 한명도 못봄
-
신기하네
-
이정도면 어디가요?
-
나 초6때 메인글 마냥 과외쌤한테 존나 폐급짓했네 ㅋㅋㅋㅋㅋㅋㅋ
-
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 자살
-
통과 노베입니다 ebs통과듣다가 뭔소린지 모르겠어서 메가 들으려고요 장풍t를 많이...
-
정시 스나 1
문과 평백 80정도입니다. 학과 상관없이 스나 하고 싶은데 추천해줄 대학 있나요?...
-
보통 어디들 가나요 오르비기준x
-
44256 5
어디갈수 있을까요 수시당연히붙을줄 알았는데 떨어져서 이제 정시알아봐요.. 연대원주...
-
냥대 문과로 갈 수 있었네 안되겠다 내년에 반수 박아야겠다
-
ㄹㅇ 빠를듯
-
겨울방학만 다닐거라서 상담신청같은거 아예 다 신청안함했는데 괜찮겠죠??
-
사탐 개념강의 2
정법을 2학년때 선택해서 1년동안 내신대비하며 개념은 다 한번 하긴했는데(강의x...
-
입금해라 2
덕코로 받겠다
-
아무래도 재수열차 타야겠네요
-
457 게이임? 1
다군 근데 쓸게없음
-
최저 3합 4 맞췄고 어제 확인해보니 내신도 합격권이었음. (1.5후반까지 추합이...
parametric search인가
오 맞아요
매개변수 탐색이 맞왜틀 잘당함 디테일때문에
진짜 그 디테일 놓치면 몇 시간이고 고생하는 케이스가 많더라구요.. 참 겸손해지는 파트인 듯 합니다,,
열심히하세요 ㅎㅎ
요즘 제가 약한 dp문제들을 bottom up 방식으로 풀어보는 연습을 많이 하고 있는데 이런 주제도 있었군요 참고하겠습니다
dp… 화이팅입니다 :)