컴공 일기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를 선물하세요.
-
진지함뇨
-
요즘뭐하심뇨? 2
ㅈㄱㄴ 연고대 이명학 설경 연대식
-
놀라서 두각수업중에 허겁지겁 달려온 션티쌤이면~>개추 오늘 세정수업 너무...
-
성대는 추가합격도 문자주나요??
-
나름 학군지에서 인강패스도 끊고 시대나 러셀 단과 한두개 들으면서 사교육 많이...
-
비슷한 과라고 가정하거나, 고대 세종이 더 과가 높을때 전과 등등을 생각한다면 어디가 좋을까요?
-
-
메가스터디 환급 1
이렇게 뜨면 끝난 건가요?? 멀 더 해야하는지 모르겠네용
-
한약학과 라인 9
본인 약대 1-4칸 서성한 애매 성적이고 서울대 안됨 서울대 낮과랑 경희 한약이...
-
(서울대 합격 / 합격자인증)(스누라이프) 서울대 25학번 단톡방을 소개합니다. 0
안녕하세요. 서울대 커뮤니티 SNULife 오픈챗 준비팀입니다. 서울대 25학번...
-
디지털은 감가도 그렇고 감성도 없고
-
저는 여자인데 일단 진로가 없구요 수능때 물화는 선택안해서 거의 잘 모릅니다 일단...
-
-
흠
-
5칸 1
20명 뽑는 학과입니다. 괜찮을까요..?
-
시대인재 재종 환영키트에 검은 만년필을 받은 꿈..
-
연세대학교, 건국대학교 여기는 안하면 바보빙딱입니다 ㄹㅇ ㅋㅋ
-
-
가능할까요?
-
언제가 시즌이죠?
parametric search인가
오 맞아요
매개변수 탐색이 맞왜틀 잘당함 디테일때문에
진짜 그 디테일 놓치면 몇 시간이고 고생하는 케이스가 많더라구요.. 참 겸손해지는 파트인 듯 합니다,,
열심히하세요 ㅎㅎ
요즘 제가 약한 dp문제들을 bottom up 방식으로 풀어보는 연습을 많이 하고 있는데 이런 주제도 있었군요 참고하겠습니다
dp… 화이팅입니다 :)