공부공간

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 사냥꾼의 사정거리를 계산할 때에, 동물에서 가장가짜운 사대의 왼쪽 오른쪽만 보면된다. 전체탐색 x 이분탐색으로 사대의 위치를 찾고, 정확히 찾는다면 L값이 Y값보다 같거나 큰지의 여부를 파악하고, 찾지못했다면, 양옆의 사대의 X값의 차이 + y 값이 L사정거리보다 같거나 작으면 범위안에 있는 것이다. import java.io.BufferedReader;..

https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 세용액의 합이 0 이 가까운 것은 고르기 위해서, 정렬후 앞쪽부터 O(n)만큼 순차탐색을 하도록하자. 세개의 포인터를 사용해야하기때문에, 하나는 고정시키고 두개를돌려주자 5000^2으로 충분하다 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java...

https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다. www.acmicpc.net 서로다른 지점에 공유기를 설치하면서 가장 멀리 떨어지게 설치하는 거리를 구하는 문제이다. 첫번째에 놓았다면, FOR문을 돌면서 나머지와의 거리를 계산해주고 CNT로 그 값을 반환하여서 C와 비교하면서 거리값인 MID를 이분탐색으로 업데이트해준다. 처음에 LEFT 를 배열중 가장작은값으로 초기화 시켰는데 틀렸습니다가 나와..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기을 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따 www.acmicpc.net 이분탐색으로 나무를 자르는 문제이다. 절단기의 H를 설정해주면 나무배열에서 H이상의 값을 가진나무들과 H의 차만큼 가져갈수있는 나무가..

N개의 지방에게 알맞는 예산을 분배하는 문제이다. 입력의 마지막에 돈이 주어지는데, 각자 원하는금액을 최대한 맞추어주면서, 내가가지고있는 금액 한도에서 분배해야한다. 즉, 요청값을 정렬한 후에 이분탐색으로 적절한 예산을 찾아주면된다. 두가지의 예외가 존재하는데, 1. 예산이 너무 많아서 모두 원하는만큼 주어도 되는경우 2. 예산이 너무 적어서 원하는금액중 가장 작은 금액으로도 못주는경우 만 이분탐색 전에 체크해주면된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57..