컴공 일기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를 선물하세요.
-
강기분도 삿음
-
마플 902문제 중고서적에서 골라 어제 샀고 오늘 다 풀었음 이제 지적유희용...
-
영어대학도 있고 영미문학도 있던데 영미문학이 영문학이라고 보면 되나요….?
-
초딩때인데 화장실 씻고 나왔는데 여자 담임쌤이 있었음.
-
장학금 ㄱㄴ? 2
진지하게 쓸건데
-
시발 쨔스 2
171130풀었다..
-
덕담해드림
-
모두들 뉴스 읽고 댓글 보기전에 각자 의견 정리하고 들어갑시다 4
안그럼 댓글알바들의 필력에 선동당함
-
뭐라도해야하는데
-
-
6모 찍맞 3 9모 5 수능 3인데 지금 시점에서 시발점 빠르게 돌리는게 나을까요...
-
뇨뇨이 3
(뭔뜻인지모름)
-
이번 수능 4뜬 완전 노베인데 노베가 듣기에 많이 어려움? 김승리 말고 추천하시는 분 있나요..??
-
진학사 267 1
어딘가 일그러진 3합 15 어케 생각하시나요
-
개념+유형 해주려는데 걍 쎈해주면 됨? 아예 처음하는 학생임
parametric search인가
오 맞아요
매개변수 탐색이 맞왜틀 잘당함 디테일때문에
진짜 그 디테일 놓치면 몇 시간이고 고생하는 케이스가 많더라구요.. 참 겸손해지는 파트인 듯 합니다,,
열심히하세요 ㅎㅎ
요즘 제가 약한 dp문제들을 bottom up 방식으로 풀어보는 연습을 많이 하고 있는데 이런 주제도 있었군요 참고하겠습니다
dp… 화이팅입니다 :)