https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 이분탐색 문제이다. 세 수를 선정할 때에, O(N^3) 브루트포싱으로 접근하면 시간초과를 받게 되므로 세 숫자 중 하나는 이분탐색을 통해서 골라내야 한다. O(N^2) 로 두개의 쌍을 더해서 그 합 SUM 을 만들어 주고, SUM의 음수와 가장 가까운 수를 이분탐색으로 구해준 다음 셋의 합이 0에 가까워지도록 갱신해나가면 된다. 이때, lower_bound로 구한 인덱스가 k..
https://www.acmicpc.net/problem/1561 1561번: 놀이 공원 첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 www.acmicpc.net 이분 탐색 문제. N이 터무니 없이 큰 숫자라서 시뮬레이션 문제로 보면 시간초과를 피할 수 없다. 이분탐색을 통해서 "사람 N명이 탑승하는데 필요한 최소의 시간" 을 구한다. 이 시간을 T라고 하면, 정확히 T 시간에 사람이 N명 탑승하게 될 것이므로, T-1 시간에는 탑승을 하지 못한 사람들이 생기게 된다. 이 사람들 중에서 마지막 아이가 나오게 되므로, T..
https://www.acmicpc.net/problem/2295 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 말이 세 수의 합이지 브루트포싱하면 O(N^4)이다... 세 수의 합 d와 배열 안의 어떤 수 U가 같아지는 경우를 찾아야 한다. 브루트포스로 접근했을 때 세 수가 O(N^3), U와 매칭시키면서 O(N)이므로 전체 시간복잡도가 O(N^4)가 되어서 시간초과를 받는다. 밋인더미들 알고리즘을 사용해서 선택해야하는 네 수 (세 수 a,b,c 와 U) 를..
https://www.acmicpc.net/problem/3649 3649번: 로봇 프로젝트 각 테스트 케이스마다 한 줄에 하나씩, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2) 정답이 여러 개인 경우에 www.acmicpc.net 이분탐색 문제 std::unordered_map 쓰면 날로먹을수있을거같이 생겨먹었는데 왠지 모를 이유로 잘 안풀려서 이분탐색으로 해결했다. 둘의 합이 X*10000000 = K 가 되게 해야하기 때문에, 어떤 한 수를 정해줬다면 해당 수와 더해서 K가 되게끔 하는 수를 O(logN) 시간에 찾아야 한다. 찾아내는 가장 좋은 방법은 이분탐색. 이때, 어떤 한 수 a가 한개밖..
boj 1182 부분수열의 합 에서 범위를 두배로 키운 문제. https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 밋인더 미들 알고리즘을 사용한다. boj 1182에서와 같이, N이 20일때는 모든 경우에 대해서 브루트포싱할때 전체 연산 횟수가 백만 정도여서 깔끔하게 해결이 가능하지만, N이 40인 이 문제에서는 전체 연산 횟수도 백만의 제곱이어서 시간초과를 받게 된다. 시간초과를 방지하기 위해 입력으로 들어..
https://www.acmicpc.net/problem/8983 8983번: 사냥꾼 입력의 첫 줄에는 사대의 수 M (1 ≤ M ≤ 100,000), 동물의 수 N (1 ≤ N ≤ 100,000), 사정거리 L (1 ≤ L ≤ 1,000,000,000)이 빈칸을 사이에 두고 주어진다. 두 번째 줄에는 사대의 위치를 나타내는 M개의 x-좌 www.acmicpc.net KOI 2013 중고등부 1번 사대에서 맞출수 있는 동물을 매칭하면 O(NM)으로 시간초과를 받는다. 각 동물들에서 가장 가까운 사대를 O(lgM) 으로 매칭하고 이를 O(N)번 반복해서 전체 시간복잡도가 O(NlgM)이 되게하는게 정석적인 풀이 가장 가까운 사대를 O(lgM) 에 매칭하는데 있어서, 이분탐색을 사용해야 한다. V에서 K 이..