컴공 일기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
보통 어느정도 걸리나요.. 24일에 결재했는데 아직 안 왔네요 ㅠㅠ
-
에타 보니깐 다 하지 말라고 하고
-
이명학보다 잘가르침?
-
지금쯤이면 표본 0
거의 다 찬건가요?
-
성적은 지움 원하는 과목 있음?
-
이시간에자면 내일 일어나서 하기엔 업뎃시간때메 엄청 촉박할것같은데 할건하고자야겟죠? ㅎㅎㅎ
-
업로드가 느려서 작년강의 듣고 싶은데 그냥 올해꺼 느려도 따라가는게 맞을까요?
-
진학사를 돌려보는게 처음인데... 등수에 왜 이리 사람이 없는거죠??
-
아취한가 16
ㅋㅋㅋㅋㅋㅋㅋ
-
죄송해요 0
고대 모학과 방뺄게요 ㅈㅅ
-
학벌 욕심 25
재수 할때 아무생각없이 꾸준히 기계같이 공부햐야한다고 하지만..저는 동기부여 없이는...
-
신기하긴 한게 12
보추 여장 글 좀 올리니 내가 남르비인 줄 아는 거임ㅋㅋㅋㅋ
parametric search인가
오 맞아요
매개변수 탐색이 맞왜틀 잘당함 디테일때문에
진짜 그 디테일 놓치면 몇 시간이고 고생하는 케이스가 많더라구요.. 참 겸손해지는 파트인 듯 합니다,,
열심히하세요 ㅎㅎ
요즘 제가 약한 dp문제들을 bottom up 방식으로 풀어보는 연습을 많이 하고 있는데 이런 주제도 있었군요 참고하겠습니다
dp… 화이팅입니다 :)