컴공 일기260
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를 선물하세요.
-
-
한양의인데 이거 설마 탈출해야 해서 강제 +1 해야하게 되는건 아니겠지
-
리트 언어이해 지문 분석해보라고 했더니 문장 단위로 이렇게 해주네요...
-
1컷 47 에서 50을 진동한다는건 쉽게 문제를낸단거임 그리고 개념양이 적어서 실전공부할시간이 많음
-
올해도 입시 실패하면 운지하러 갑니다.
-
대충계획 8
설대결과 나오기 전까지 칼럼 마구 써놓기 설뱃나오면 하나씩 업로드 명성 이용해서...
-
암거나 ㄱㄱ
-
알바가ぎしろよ 5
왜 또 알바가야함
-
ㅅㅌㅊ?
-
국어 1타는 누구인가 10
-
전적대 학과가 컴공이어서 인원이 엄청 많았어요여자친구랑 과CC였는데 전공수업도 같이...
-
페이커 월즈 5회 우승하게 해달라고 빌었음 그래서 신 원망 안할거임요 나중에 교회도...
-
히히
-
인증...? 6
엄청 흔들린 사진으로 하나만...
-
호떡 먹고 싶어요 14
여행가서 먹은 그 맛이 잊혀지지 않네요 주변에 호떡 파는 곳이 없어서 울엇어...
-
고교 경제(수능출제범위)랑 경제원론(1학년/맨큐)이랑 내용이나 범위 많이 달라요?...
-
ㅇㅈ 15
실시간 저녁 ㅇㅈ
-
한번 만나볼 여르비 구해요~
-
저도 끼고싶어요
-
오르비 쪽지 : 앱 없으면 알림이 안 떠서 불편 그나마 이거 많이 씀 오픈카톡 :...
parametric search인가
오 맞아요
매개변수 탐색이 맞왜틀 잘당함 디테일때문에
진짜 그 디테일 놓치면 몇 시간이고 고생하는 케이스가 많더라구요.. 참 겸손해지는 파트인 듯 합니다,,
열심히하세요 ㅎㅎ
요즘 제가 약한 dp문제들을 bottom up 방식으로 풀어보는 연습을 많이 하고 있는데 이런 주제도 있었군요 참고하겠습니다
dp… 화이팅입니다 :)