컴공 일기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
어렸을때는 엄스라이팅 할머니 가스라이팅 당해서 내가 잘생긴줄 앎 ㅋㅋ
-
아가 자야징 10
모두 잘장
-
학교 시험때 앞자리 애가 자면서 계속 방귀 껴서 지옥이었음 하필 방귀소리도...
-
자라 3
나는 잔다
-
학생이 불만 같은 거 강사 카페에 올리면 누군지 알아내서 뒷담 ㅈㄴ 깐다던데 이게 맞음???
-
실지원 표본 숨기신 분들 많으려나요 투표 부탁드려요 이거 숨기신 분들 많으면 표본...
-
부거 시킴 6
부거
-
위로는 그 사람이 진짜 최악의 상황에선 어느 정도 벗어났을 때 하는 거고 한참...
-
서울대 노리는 애들은 물1 화1 화2 물2 중에 해야하는데 일단 서울대 노리는데...
-
수시 넣을 때 구관으로 넣었는데 성적순으로 기숙사 된다는 걸 이제 들어서......
-
뭐야 정모메타? 0
줌켜주세요
-
중학교 3년+고등학교 3년보다 재수학원에서 N수하던 시절이 더 즐거웠어요 사람들...
-
점심시간에친구랑답맞추기 밥존나쳐먹고배아프기...
-
미적분 노베가 미적분 제대로 떼려면 재수 각오해야 한다고 하던데 7
ㄹㅇ인가요?
-
상처만 남는다…..
-
라이더 드라이브 재밌으니까 꼭 보세요
-
대충 100명 넘어가는 대형과인데요 나군이고 157등이고 4칸나오는데 넣어볼만 할까요.. 자전입니다
-
생윤 최대 단점 19
수능 전주까지 인강듣고 앉아있어야 함 실모벅벅? 그딴 거 없음 그리고 올해 생윤도...
parametric search인가
오 맞아요
매개변수 탐색이 맞왜틀 잘당함 디테일때문에
진짜 그 디테일 놓치면 몇 시간이고 고생하는 케이스가 많더라구요.. 참 겸손해지는 파트인 듯 합니다,,
열심히하세요 ㅎㅎ
요즘 제가 약한 dp문제들을 bottom up 방식으로 풀어보는 연습을 많이 하고 있는데 이런 주제도 있었군요 참고하겠습니다
dp… 화이팅입니다 :)