Algorithm/매개변수 탐색

[틀림] 프로그래머스 징검다리 // 매개변수 탐색

https://school.programmers.co.kr/learn/courses/30/lessons/43236 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr* 풀이완탐 -> 50000Cn -> 불가매개변수 탐색f(x) : 최소거리가 x일때, 제거대상 바위수가 n 이하인가?prev 변수가 킥이다.#include using namespace std;int ret,n; int dist;vector rocks;int go(int x){ int cnt=0; int prev=0; //이전위치 for(auto rock : rocks){ //제거대상 if(abs(prev-..

[틀림] 백준 1561 놀이공원 // 매개변수탐색, ret-1 추가탐색

https://www.acmicpc.net/problem/1561* 풀이처음보는 형태의 문제ret 값을 찾은후, 추가 계산이 필요하다.왜냐면 , 찾은 ret 값은 n명 이상을 태울수있는 최소시간이다.딱 n명을 태우는 시간이 아니다.nret를 찾고, ret-1분에서 탄사람수 계산ret분에서 놀이기구를 순회하면서 정확히 n번째 사람 찾기 * 전체코드#includeusing namespace std; typedef long long ll;ll ret, n,m;ll a[10000+4];int go(ll x) { ll temp=m; // 시작하자마자 m 명 태우고 시작 // temp : 태운사람수 for(int i=0;i=n;}int main(){ ios_base::sync_with_stdio(0)..

[틀림] 백준 14627 파닭파닭 // 매개변수탐색, 나머지 구하기

https://www.acmicpc.net/problem/14627* 풀이어려웠던점각각 원소에대해 순회하면서 나머지를 더하는 방식의 문제아래의 경우, 답이 0이 되어버림개선순회대신, sum을 구하고파길이의 전체합(sum) - (최적의파갯수 * 주문받은 파닭수) 하면 됨sum - (ret*c)를 출력 하면 됨.ex) 1020 - ( 175 * 5 ) = 145#includeusing namespace std; typedef long long ll;ll ret, s,c;ll a[1000000+4];int go(ll x) { ll cnt=0; for(int i=0;i=c;}int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ..

[맞음] 백준 16434 드래곤앤던전 // 매개변수 탐색, long long, 선빵

https://www.acmicpc.net/problem/16434* 풀이어려웠던점long long일때, en값을 정하는부분LLONG_MAX 를활용 or 1e18로 해도됨용사가 선빵을 때린다는점n회 공격이 필요한경우, n-1회만 맞으면됨n번째 공격에서는 몹이 죽어서 공격을 받지 않음여기서 용사가 공격받지 않는다는 사실을 추론해내야함.#includeusing namespace std; typedef long long ll;struct A { ll t,a,h;};ll n,atk;ll ret;vector v;//최대피가 x일때, 되는지bool go(ll x, ll atk) { ll tmp=x; //초기 최대피 for(int i=0;itmp) x=tmp; //최대 hp 초과 불가능 } }..

[세모] 백준 6236 용돈관리 // 매개변수 탐색

https://www.acmicpc.net/problem/6236 * 풀이1문제가 좀 난해했다. 반복인출 x통장에 남은돈을 사용할수 없음. 무조건 집어넣어야함. x원만 가능.반복인출 불가능 -> 안되는 경우 예외처리 추가go함수#includeusing namespace std; int n,m,ret;int a[100000+4];int go(int x) { // 인출할돈이 X 일때, 가능한지 //인출할돈보다 써야할돈이 크면 반드시 실패 for(int i=0;i x) { return 0; } } int cnt=1; //인출한 횟수 int remain=x; // 남은돈 for(int i=0;i>n>>m; for(int i=0;i>a[i]; } int..

[틀림] 백준 2343 기타레슨 // 매개변수 탐색, 음수기반 카운팅

https://www.acmicpc.net/problem/2343* 풀이완탐 : 이중 for문이분탐색 : 첫번째 for문을 이분탐색으로 교체 go 함수 구현이 빡센문제f(1)이 거짓이 나와야 되는 문제 발생예외처리 필요어떤 강의가 블루레이보다 긴경우, 무조건 false를 반환하도록 처리 필요.강의 중 하나라도 Blu-ray 용량보다 긴 경우, 해당 용량(x)은 적합하지 않으므로 무조건 false를 반환.en= mid-1st = mid +1음수기반 카운팅 필요양수기반은 case가 많아져서 너무 복잡// x : 빼고 남은크기int temp = x; // 블루레이의 크기 저장int cnt = 0;for(int i = 0; i  초기화 주의최대 길이 = 10000분 * 최대갯수 여야함int st=1;int en..

[세모] 백준 2792 보석상자 // 이분탐색, 매개변수탐색

https://www.acmicpc.net/problem/2792* 풀이 헤맸던부분질투심이 x 일때, 학생수를 계산하는 idea그림으로 그려보자st,en을 디버깅 찍어가면서 수정 (st+en) or (st+en+1)#includeusing namespace std; int n,m;int a[300000+4];int go(int x) { int cnt=0; // 필요한 학생수 for(int i=0;i>n>>m; for(int i=0;i>a[i]; } int st=1; int en=pow(10,9); while(st

[Algo] 공유기설치 c++ // 매개변수 탐색 hard

* 의사코드행동영역f(x) 정의시 최대, 최소를 쓰지마라. 우리는 이문제를 결정문제로 바꿔서 풀어야한다.간격을 고정하고 탐색하라. (x)로 고정.되는지를 구현하는게 사실 핵심이다. (go 함수)참인경우, st = mid 임에 주의 // en = mid 아님!go 함수 구현완탐하면서 간격    설치(cur갱신) , cnt+1설치된 공유기 갯수가 c 보다 큰지 return//설치간격이 x 일때, 공유기 c개 이상 설치 가능한지ll go(ll x) { ll cur = arr[0]; //현재 설치된 위치 ll cnt = 1; //공유기 설치갯수, 1st는 항상설치 for (int i = 1; i = c;}f(x) 정의, go 함수 구현 모두 빡센 문제였다.f(x)를 현재간격으로 "고정" 하고간격..