본문 바로가기

이분 탐색

BOJ)5846 Tractor 문제: icpc.me/5846 n^2의 격자에서 한 점에서 4방향으로 일정 조건(둘의 차이가 k이하이면 이동 가능)을 만족하면 이동가능할 때임의의 한점을 잡아 반 이상의 격자를 순회할 수 있는 최소의 k를 찾는 문제이다. 최대중의 최소를 구하는 문제이므로 파라메트릭 서치를 생각해볼 수 있다.이 때 k를 mid값으로 정해놓은 뒤에 만족 여부를 확인하게 되는데만족여부는 dfs를 통하여 확인할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #include #include using namespace std;int n, a[555][555], b[555][555];int dx[] = .. 더보기
BOJ)5842 Partitioning the Farm 문제: icpc.me/5842 n*n 격자가 주어질 때 주어진 격자를 가로나 세로로 k번 분할 할 수 있다. 분할 된 각 부분들의 합의 최댓값의 최솟값을 구하는 문제이다. 최대중에 최소를 구하는 문제이므로 파라메트릭 서치로 접근할 수 있다. 다만 격자에서 처리해야하는게 좀 까다로울 수 있는데 n이 15밖에 안되므로 2^15의 모든 경우로 세로 격자를 세워준 뒤 파라메트릭 서치로 가로 격자를 세우며 답을 구할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include #include #include using name.. 더보기
BOJ)14434 놀이기구1 문제: icpc.me/14434 놀이기구를 타는 키 제한이 존재하고 각 날마다 키가 자라는 아이와 어떤 놀이기구를 타는지 물어보는 질의들이 주어질 때 각 날마다 아이들이 타는 놀이기구의 수를 출력하는 문제이다. 이 문제는 각 질의에 대하여 해당 놀이기구를 탈 수 있는 첫번 째 날을 구해주면 그 날 이후는 해당 놀이기구를 항상 탈 수 있으니 psum으로 해결 가능하다. 문제는 질의마다 첫번 째 놀이기구의 탑승 가능일을 구해주는 일이다. 우선 질의에 대해 첫번 째 놀이기구의 탑승 가능일을 탐색해야하므로 mid값을 날짜로 생각을 하자. 그럼 mid일에 놀이기구를 타야하는 두 아이의 키를 가져와야 하는데 이는 2차원 벡터로 각 아이에 대해 키가 크는 날짜를 벡터에 삽입해준다면 upper_bound로 계산해줄 수.. 더보기
BOJ)9460 메탈 문제: icpc.me/9460 최대중의 최소를 구하는 문제이므로 이분탐색으로 해결할 수 있다. 이 때 검사 조건은 현재 보고 있는 점들의 집합의 최솟값과 최댓값의 차이의 1/2이 mid보다 큰지 확인해주어 클 경우 새로운 수평터널을 생성하면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142#include #include using namespace std;int t, n, k;pair dat[10001];bool posb(double maxdist) { double minn = dat[0].second; double maxx = dat[0].second; int cnt = 1; for (int i = 1; i 더보기
BOJ)3079 입국심사 문제: icpc.me/3079 X시간 동안 심사할 수 있는 인원 수는 Sum(i: 0~N) X/T[i] 로 정의할 수 있다. 이를 이용하여 파라메트릭 서치로 답을 구해주면 된다. 123456789101112131415161718192021222324#include #include typedef long long ll;using namespace std;ll n, m, a[100001];int main() { scanf("%lld%lld", &n, &m); for (int i = 0; i 1; ll cnt = 0; for (int i = 0; i = m) hi = mid; else lo = mid + 1; } printf("%lld\n", lo); return 0;}cs 더보기
BOJ)7579 앱 문제: icpc.me/7579 최소한의 비용을 사용하여 m만큼의 메모리를 얻을 때 비용을 출력하는 문제이다. dp[pos][cost]= pos번째 앱까지 cost만큼의 비용을 사용해 얻을 수 있는 메모리의 최댓값으로 정의 한 뒤 파라메트릭 서치를 이용하여 cost값을 조정해주면 된다. 12345678910111213141516171819202122232425262728293031323334#include #include #include using namespace std;int n, cost, m[101], c[101], dp[101][10001];int func(int pos, int cos) { if (pos = 0) ret = max(ret, func(pos - 1, cos - c[pos]) + m.. 더보기
BOJ)1745 숨기 문제: icpc.me/1745 F개의 방이 있을 때 각방마다 학생들이 숨을 수 있는 수와 현재 몇명의 학생들이 있는지 수가 주어진다. 이 때 방 A에서 B로 이동할 때 걸리는 시간이 주어질 때 모든 학생이 숨을 수 있는 최소 시간을 구하는 문제이다. 우리는 소스 -> I번 방 -> I번 방에서 ->J번 방으로 연결 된 정점 -> J번 방 ->싱크로 모델링을 하여 모든 학생들이 숨을 수 있는지 여부를 알 수 있다. 이때 capacity를 소스 -> I번 방은 현재 i번방에 있는 학생 수 / J번 방 -> 싱크는 j번 방에 숨을 수 있는 학생 수 나머지는 INF를 주면 된다. 이렇게 하여서 흘린 maximum flow가 현재 있는 학생들의 수의 총합과 같다면 현재 모델링에서 학생들이 전부 숨을 수 있는것이다.. 더보기
BOJ)2512 예산 문제:icpc.me/2512 최소중의 최대를 구하는 전형적인 파라메트릭 서치 문제이다. 다만 주의해야 할 건 모든 인풋 a[i]의 합이 m보다 작을 경우 a[i]중에 최댓값을 출력해줘야 하는 예외 케이스가 있다. 123456789101112131415161718192021222324252627282930313233343536#include #include typedef long long ll;using namespace std;ll n, a[10000], m, lo, hi, ma, s;int main() { scanf("%lld", &n); for (int i = 0; i = s) { printf("%lld\n", ma); return 0; } lo = 0; hi = 21000000000; while (.. 더보기
BOJ)11973 Angry Cows 문제: icpc.me/11973 Angry Cow를 x위치에 던지면 [x-R,x+R]위치의 건초가 모두 파괴된다. N개의 건초더미의 위치가 주어질 때 K마리의 Angry Cow를 던져서 모든 건초를 파괴하려할 때 R의 최솟값을 출력하는 문제이다. 우리는 건초더미들의 위치를 구간으로 생각하여 한 Angry Cow가 구간 2*R을 파괴할 때 K마리의 Angry Cow가 전체 구간을 다 파괴할 수 있는지를 확인하여 R의 최솟값을 구해야한다. R의 최솟값은 이분탐색을 통하여 구할 수 있다. 123456789101112131415161718192021222324252627282930313233#include #include using namespace std;typedef long long ll;ll n, k, .. 더보기
BOJ)2022 사다리 문제: icpc.me/2022 극혐스러운 수학문제이다. 사실 그렇게 어려운 수식은 아니고 직선의 방정식 두개를 구하여 두 교점의 y좌표인 c를 알고 있으니 이때 구해야하는 밑면 m을 이분 탐색을 통하여 찾아 나가는 문제이다. 밑면m이 클수록 c는 낮아지므로 함수로 구한 값이 c보다 크다면 lo를 mid로 c보다 작다면 hi를 mid로 잡아주면 된다. 사실 이터레이터를 얼마나 돌려야되는지 감이 안와서 제출하면서 조절했는데 너무 많이 돌리면 TLE를 보게되고 너무 적게 돌리면 오차때문에 WA를 보게된다. 123456789101112131415161718192021222324252627#include #include using namespace std;double x, y, c, lo, hi;double fx.. 더보기