컴공 일기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를 선물하세요.
-
가고싶다..
-
길 가다가 고등학생들 보면 난 이제 수능 안 봐도 된다고 생각하니까 갑자기 삶이 즐거워진 기분
-
-
(나)가 발명이라는건 인정하는데 그 전에 자극전파가 맞지않나요? 해설에선 발명이라서...
-
키작고귀엽고하얗고슬랜더인 사람이랑 연애하고 싶다
-
여친대행이라도 구할까
-
한지 세지 1
중 하나를 선택하려고 하는데, 만점 받기 뭐가 더 좋나요? 현재는 노베입니다....
-
17317071 3
먼 뜻이게
-
오르비 끄고 6
히토미 봐라
-
원솔멀텍 한완기 4점기출 노베임
-
현장복기본이었음
-
논술 딸깍이면 국어 7등급도 메이저의대 가능하다니까 심지어 apple bus 몰라도...
-
대학 강의 듣고 대학이 왜 수시 좋아하는지 알 것 같기도 6
데이터 시이언스 관련 동영상 강의 듣는데 편미분 그라디언트 나블라 공분산 확률변수...
-
절제만 잘한다면 ㅇㅇ
-
아이 했슴다 2
https://orbi.kr/00072562421/ 육진 방언의 특징으로 '아니'를...
-
풀다가 이해가 안 돼서 오른쪽을 봤단 말이죠. 표에 나온 건 자기장 세기잖아요....
-
아직 탈릅안하셨어요 닉네임 바꾸심
-
90 77 97 43 23 33 탐구 생윤사문 반바퀴 돌리다 국수 정상화가 필요함을...
-
왜 울고있냐 2
궁상맞게 뭐가 힘들다고
-
죽고싶어도죽지는말고~
parametric search인가
오 맞아요
매개변수 탐색이 맞왜틀 잘당함 디테일때문에
진짜 그 디테일 놓치면 몇 시간이고 고생하는 케이스가 많더라구요.. 참 겸손해지는 파트인 듯 합니다,,
열심히하세요 ㅎㅎ
요즘 제가 약한 dp문제들을 bottom up 방식으로 풀어보는 연습을 많이 하고 있는데 이런 주제도 있었군요 참고하겠습니다
dp… 화이팅입니다 :)