컴공 일기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를 선물하세요.
-
대성패스 사요 0
쿨거래 부탁해여
-
흠...
-
내가 1~2문제 맞추려고 이짓하고있는거 맞음?
-
고2 3등급 나오는 나에게 과외를 해줌
-
지금실력이면 이대는 무슨 부경대 갈까말까일거같은데 하… 국어2컷 수학3컷 영어3...
-
원래 이런가요 학교에서 수업듣는데 문제를 못풀겠어요ㅠ
-
걍 공부만 함 0
걍 공부임
-
국어서바 0
3모대비 푸신분 있음? 어땟나요
-
제1원인=진성난수 제1원인으로부터 랜덤논리가 발생, 서로 간섭, 적자생존하여 진화...
-
걍 반수하지말까 6
약대도 괜찮은 것 같은데
-
메리 크리스마스 7
-
-
독학서로 백문일답 문법백제 넘는 교재 수험생활 때나 과외 준비할 때나 못 본 거 같은데
-
햇살 들어오고 적당히 바람 불고 나른하고 좋구나... 마음 맞는 애인이랑 같이...
-
재종 담임이..데리고 있던 애중에 11353인가 나왔는데 연대 의류학과엿나 무튼...
-
ㅈㄱㄴ
-
재수고 목표는 서성한입니다 국어를 작년에 꽤나 공부를 열심히 했다고 생각했는데...
-
오... 16
못보던 사람들이 많네 물갈이 중이구나
-
오늘 볼까하는데
-
지엔장 0
믿고잇엇다구
-
08년생 자퇴하고 갈곳찾다가 발견했는데 혹시 어떤가요?
-
드걔쟤
-
승요 등장 8
대 황 삼 성
-
저녁 뭐먹지 7
흠...
-
행렬 질문.. 14
원래 앞 행렬 n열이랑 뒤 행렬 n행이랑 곱해서 스칼라로 나타내도 되는거임?
-
쌍윤 공부법 질문 - 원래 개념 강의만으로 100프로 안 되는 게 맞나요? 5
개념 강의만 보면 뭔가 개념이 빡 안 잡히는데 혼자 기출 풀고 오답 하면서 점점...
-
군생활이 ㅈ같이 지는중
-
몰라서 틀리면 배우기라도 하지 이건 증말 ;;;;
-
안녕하세요! 국어핑!!! 입니당 고3 현역 학생들의 올해 첫 풀 모의고사인 ☆3월...
-
ㅁㅊ윤사어렵다 2
그냥 담요단의정석돼서 국어2수학5영어3쌍윤11 찍고픔
-
투과목이 워낙 어렵고 표본도 그렇다고하는데도 투과목 가산점이 그렇게 큰가요?
-
이걸 대체 왜
-
실물 체감 이런거 보는데 말이 안되네요
-
-
애초에 사설이라 평소 모고보다 어려운걸로 알고있는데 한 등급 정도 차이 나나요?...
-
너무 배고픔.. 4
고기 좀..
-
[속보] 경남 산청 산불 진화대원 2명 사망…2명은 실종 2
경남 산청 산불 진화 작업에 투입된 진화대원 2명이 사망하고, 2명이 실종됐다....
-
저런데 한번도 안가봐서 가면 뭐해야될지 모름
-
국 97 수 87 영2 탐 94 (평균) 이대 초등교육 평균이라는ㄷㅔ 이정도면 대학 라인은 ㅇㄷ쯤?
-
탈릅 3
탈춤오르비
-
나트륨 칼륨 펌프 관련해서 체내 대다수의 세포의 세포막에 위치하는 일차능동수송 담당...
-
수능 때등급 9
32212정도 받으면 농어촌으로 홍익대 이상 갈 수 잇나요 국어 중간3정도여
-
그냥 화작할까 0
현역최저러라 미적언매화생 할라그랬는데 두달정도 공부해보니까 시간이 너무너무 없어서...
-
너무 이상한가요 학교에선 잉강못봐서 한완수하고 집에선 꾸줒히 인강들어나가려고하는데
-
지금 훈련도감 듣고 있는데 수특 문학 강의도 괜찮나요?
-
인생은 운이다 2
운을 이길수있는건 끈기뿐이다 운이 올때까지 끈기로 버티는거다 -토스 ceo- 오...
-
미적수학 높3?중간이상3이고 국2영1탐구11정도면 어디정도인가요?제가 라인을...
-
언미사탐 메디컬 0
의치가 너무나 간절합니다 … 국어 수학이 3등급이라 공부 시간 확보를 위해서는...
-
-
공부 ㅈㄴ 하기 2
걍 ㅈㄴ 함
parametric search인가
오 맞아요
매개변수 탐색이 맞왜틀 잘당함 디테일때문에
진짜 그 디테일 놓치면 몇 시간이고 고생하는 케이스가 많더라구요.. 참 겸손해지는 파트인 듯 합니다,,
열심히하세요 ㅎㅎ
요즘 제가 약한 dp문제들을 bottom up 방식으로 풀어보는 연습을 많이 하고 있는데 이런 주제도 있었군요 참고하겠습니다
dp… 화이팅입니다 :)