이분 탐색

문제https://www.acmicpc.net/problem/2512풀이이분 탐색 간단한 이분 탐색 문제. 상한액을 이분 탐색으로 찾으면 된다.start를 1, end를 예산요청액 중 최댓값으로 설정한다.mid를 (start + end) / 2로 설정한다.mid를 상한액으로 설정했을 때의 현재 합계를 구한다.mid보다 작은 예산 요청액은 그대로 sum에 더한다.mid보다 큰 예산 요청액은 mid만큼을 sum에 더한다.sum과 M을 비교하여 start와 end 값을 조정한다. start가 end를 넘을 때까지 진행한다.코드#include #include #include #include #include #include #include #include #include #include #include #incl..

문제 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net 풀이 이분 탐색 문제이다. 세 수의 합을 4중 for문을 이용하면 시간복잡도가 O(N * N * N * N)으로 당연히 시간초과다. x + y + z = k x + y = k - z x + y + z = k는 x + y = k - z와 같다. 여기서 x + y를 2중 for문으로 미리 구해둔다. 미리 구한 합에서 k - z를 만족하는 값을 이분탐색으로 찾으면 시간복잡도가 O(N * N * log(N))이 므로..

문제 풀이 누적 합과 이분 탐색을 사용한다. 피자 조각의 최대 개수는 1000개 이므로 O(N * N)으로 해도 시간초과가 발생하지 않는다. A와 B에서 얻을 수 있는 모든 피자 조각을 계산한다. 피자 조각은 끝과 처음이 연결될 수 있으므로 유의해서 더해야 한다. A에서 얻을 수 있는 피자 조각을 기준으로 P와의 차이만큼의 B의 피자 조각의 수를 이분 탐색으로 구한다. 코드 #include #include #include using namespace std; vector A; vector A_parts; vector B; vector B_parts; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(nullptr); int P; int m,..

문제 풀이 이분 탐색을 사용한다. 모두 탑승하는데 소모되는 최소 시간을 이분 탐색한다. 최소 시간은 0, 최대 시간은 (N X 최장 운행 시간)으로 설정했다. mid값을 이용해서 해당 시간 동안 몇 명이 탑승할 수 있는 확인한다. 여기서 주의할 점이 0초 때, 이미 기구에 탑승하고 있기 때문에 현재 탑승한 아이의 수를 미리 N으로 세팅해줘야 한다. 이분 탐색으로 얻은 최소시간은, 마지막 아이가 놀이기구에 탑승한 시점의 시간이다. (최소시간 - 1)분 때, 총 몇 명이 탈 수 있는지 확인한다. (최소시간 % 탑승시간 == 0)이라면 해당 놀이기구에는 최소시간 시점에 탑승할 수 있는 놀이기구이다. 인덱스가 작은 순으로 해당 검사를 하면서 총 탑승한 아이의 수가 N과 같을 때의 인덱스를 출력한다. 코드 #in..

문제 풀이 이분 탐색을 사용한다. 가장 긴 증가하는 부분 수열을 찾는 문제이다. 내가 알던 방법은 O(N * N)으로 전체 계산 수가 16억이 되어 시간 초과가 발생한다. 입력이 들어오면서 검사를 실시한다. 입력값이 현재 수열의 가장 끝에 있는 수를 초과한 경우 바로 수열에 추가된다. 이하일 경우엔 이분 탐색을 실시한다. 현재 수열에서 입력값 이하의 값 중, 최댓값을 입력값으로 교체한다. 이렇게 하면 시간 복잡도가 O(N * logN)으로 줄어든다. 코드 #include #include #include using namespace std; vector nums; // 기존에 입력된 nums에서 num 이하의 값중에서 // 최댓값을 num으로 교체한다. void binary_input(int num) { ..

문제 풀이 이분 탐색을 사용한다. 입력으로 주어지는 수가 상당히 크기 때문에 이분 탐색으로 해결해야 한다. 검사받는 총 시간(mid)을 이분 탐색한다. mid 시간에 심사할 수 있는 사람의 수와 M을 비교하여 범위를 조절한다. mid 시간에 각 심사대에서 심사가능한 사람의 수는 (mid / 소요시간)이다. 코드 #include #include #include using namespace std; vector nums; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(nullptr); int N, M; cin >> N >> M; for (int i = 0; i > temp; nums.push_..

문제 풀이 이분 탐색을 사용한다. 점프할 최소거리(mid)를 이분 탐색한다. 돌 사이의 거리가 mid 미만이라면 돌을 삭제한다. 삭제한 돌의 수와 m을 비교하여 start와 end를 조절한다. 코드 #include #include #include using namespace std; vector nums; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(nullptr); int d, n, m; cin >> d >> n >> m; for (int i = 0; i > temp; nums.push_back(temp); } // 시작 지점과 끝 지점을 추가 nums.push_back(0); nums..

문제 풀이 이분 탐색을 사용한다. 용사의 최대 체력을 이분 탐색한다. 최솟값(start)은 1이며 최댓값(end)은 LLONG_MAX - 1로 설정하였다. 용사가 던전 공략에 성공하였다면 답을 갱신하고 end를 줄여서 다시 검사하고, 실패했다면 start를 늘려서 다시 검사한다. 현재 방이 몬스터 방일 경우, 용사는 몬스터를 처치할 때 까지 (몬스터의 체력 / 현재 공격력) 번(turn) 공격을 맞는다. 여기서 (몬스터의 체력 % 현재 공격력 = =0)일 경우 한 번 공격을 덜 맞는다. turn 번 공격을 맞았을 때, 체력이 0이하라면 공략이 실패한 것이며 최대 체력을 늘려서 다시 검사한다. 아이템 방일 경우, 용사의 공격력과 체력을 회복한다. 코드 #include #include #include #in..

문제 풀이 최대 범위에서 최솟값을 찾으므로 이분 탐색을 사용한다. 휴게소를 세울 거리를 이분 탐색하여 찾는다. 휴게소를 세울 수 있는 최소 거리는 중복이 안 되므로 1이다. 최대 거리는 고속도로 마지막에는 세울 수 없으므로 L - 1이다. 휴게소와 휴게소 사이의 거리를 dist라고 할 때, dist 안에서 세울 수 있는 휴게소의 수는 dist / mid이다. 단, dist % mid == 0이라면, 해당 구간의 뒤에 있는 휴게소에 중복으로 세우는 것이므로 1차감한다. 코드 #include #include #include using namespace std; vector nums; vector dists; int main() { ios_base::sync_with_stdio(0); cin.tie(0); c..

문제 풀이 이분 탐색을 사용한다. 모든 수열을 탐색하면 O(n^2)으로 시간초과이다. 각 수열의 수 마다, 다른 수와의 합과 K와의 차이의 최솟값을 찾는다. 최솟값을 찾을 때, 이분 탐색으로 최솟값을 찾고, K와의 차이에 따라 범위를 조절한다. 해당 최솟값이 현재 나온 최솟값과 같다면 answer를 증가하고 더 작다면 갱신한다. 코드 #include #include #include #include using namespace std; vector nums; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(nullptr); int t; cin >> t; while (t--) { int n, K; cin >> n >> K; for (int i..