컴공 일기260
게시글 주소: https://io.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를 선물하세요.
-
사실 한잔만 한건 아니지만요
-
어떻게 생각하심
-
삼수 할말 3
현역 수시로 건동홍 컴공 갔는데 학고반수했다가 실패함 44266에서...
-
ㅏㅔㅣㅗㅜ 6
ㅏㅣㅜㅔㅗ
-
언매는 개념강의 빨리 듣고 기출 많이 분석해보면 되나요??? 4
국어는 참 힘드네요 어떤가요???
-
테슬라 구버전 Y 4739만원 폭스바겐 ID4 3000 중후반 예상 비야디 아토3...
-
좋군요
-
헤헤 4
-
난 아무리해도 1등급이안나와 ㅠㅠ 재능없나봐 이러는데 원래 뭐든지 상위 4%라는게...
-
이 노래도 사유리상 노래였네..
-
이투스 살려주려 한건가…
-
현역 수능 국수 21이 뜬 건에 대하여 이래도 정말 재능이란 게 없나요 물론 이...
-
고3 기숙사 살 때 아무도 터치를 안 하니까 밤새 오르비 유튜브 게임 반복했음 이게...
-
-
언매랑 화작은 각자 장단점이 있어서 중상~상 난도에 표점까지 별로 차이가 안 나는...
-
난 어렸을 때 4
명문대생들이 키배 뜨고 커뮤한다는 게 말이 안 된다고 생각했어요 배울 만큼 배운...
-
생각보다 잘해주시네.. 만족스러워요
-
화통사탐으로 연높공 합격하는 점수가 어느정도 일지 궁금함
-
-
사탐런 조언 5
대성 끊을것 같은데 작년에 사문 했었고 높3 나왔음 지금 쌍윤 할지 / 쌍사 할지...
parametric search인가
오 맞아요
매개변수 탐색이 맞왜틀 잘당함 디테일때문에
진짜 그 디테일 놓치면 몇 시간이고 고생하는 케이스가 많더라구요.. 참 겸손해지는 파트인 듯 합니다,,
열심히하세요 ㅎㅎ
요즘 제가 약한 dp문제들을 bottom up 방식으로 풀어보는 연습을 많이 하고 있는데 이런 주제도 있었군요 참고하겠습니다
dp… 화이팅입니다 :)