블로그 옮겼습니다

문제 링크 이 문제는 N개의 물통이 있고 L리터의 물을 N개의 각 물통에 나눠서 채우려고 하는데,물통에는 상한과 하한이 있어서 각 물통에 채울 수 있는 물의 양은 이 상한과 하한 사이의 양이어야만 한다. 이 때 N개의 물통에 채운 물의 양 중에서 가장 많은 양과 가장 적은 양의 차이가 최소가 되도록 하고싶다.이 떄의 차이를 구하는 문제이다. 단, 들어오는 입력들은 항상 L리터를 상, 하한에 맞춰 분배할 수 있는 방법이적어도 하나는 있다고 가정한다. 일단 이 문제는 두가지의 풀이가 있다.첫번째 풀이는 라인 스위핑(+그리디)이다. 내가 대회 때 푼 방법이 이 라인 스위핑인데대회가 끝나고 보니 나 말고는 라인스위핑으로 푼사람을 찾을 수가 없었다.좋은건지 안좋은건지.. 사실 처음에 다른 풀이 방법을 떠올렸다가 ..

우선 N개의 원소를 가진 어떤 임의의 배열 X가 있고,이 안에 크기 M의 구간(subarray) A가 있다고 하자. 물론 값들은 정렬되지않은 상태이다. 이 때 A의 K번째 원소를 구하는 방법은 여러가지가 있다. 우선 내가 아는 K번째 원소를 찾는 방법들을 구체적으로 써보자면(사실 내가 파라메트릭서치라고 표현하는것도 역시 바이너리 서치인데, 구분을 위해 다르게씀)(그리고 값의 범위가 큰 경우에는 좌표압축은 이미 했다고 가정한다.)1. 벡터+sort2. k번째 원소 세그먼트트리3. k번째 원소 BIT4. BIT + 파라메트릭서치 + 바이너리서치5. 머지소트+세그먼트트리+파라메트릭서치+바이너리서치6. 2D 세그먼트트리 이것 이외에도 버킷으로 어찌저찌하는 것도있는것같은데 잘모르겠다. 이것들 중에서 쿼리가 들어와..

boj.kr/9426 \(1\leq{N}\leq{250000}\) \(1\leq{K}\leq{5000}\) \(K\leq{N}\) \(0\leq{a_i}\leq{65535}\) 이 문제는 N개의 수와 구간의 길이 K가 주어졌을 때 N-K+1 개의 연속된 구간의 중앙값을 모두 더하여 출력하는 문제이다. 중앙값의 정의는 (K+1)/2 번째로 작은 수이다. naive 하게 생각해보면 O(N)개의 구간에 대해 정렬하여 가운데값을 구하는데 O(NlgN) 이므로 O(N^2lgN)이 든다. 근데 O(N^2)도 시간안에 돌아가기 힘들다. 어떻게할까? 펜윅트리에 수가 현재 길이 K의 구간안에 하나 들어갈 때마다 수 자체를 인덱스로 1업데이트하고 구간에서 사라지면 -1업데이트하는식으로 생각해보자. 그럼일단 0번째인덱스부터..

\(1\leq{N}\leq{1000}\)\(1\leq{K}\leq{4\cdot{10^{7}}}\)\(1\leq{w}\leq{10^7}\) 4개의 반이 있고 각 반의 학생수는 N명이며, 각 학생들의 몸무게 w 가 주어진다.반 마다 한명 씩을 골라서 총 네명의 선수를 선발하는데 네 선수의 몸무게의 합이 K와 가장 근접하도록선수들을 선발하여 그 몸무게의 합을 구하는 문제이다. 만약 답이 여러개라면 그중 작은 값을 답으로한다. 우선 가장 무식하게 푸는 방법이 완전탐색을 하는 방법이며 O(N^4) 이 걸린다. N이 최대 1000이기 때문에무리가 있다. 그런데 조금만 생각을 해보면 세 개의 반에서 선수가 골라졌다면 남은 한 반에서는K와 가장 가까운 학생을 고르면 되기 때문에 K-(세 반에서 뽑은 학생들의 몸무게의 ..

https://www.acmicpc.net/problem/1044 \(2\leq{N}\leq{36}\) (N은 짝수) N을 입력받고, 10^15 이하인 자연수를 N개씩 두줄 입력받는다. N명의 사람은 1번팀 또는 2번팀에 들어간다. 각각의 사람이 어떤 팀에 들어갈 때 증가하는 팀의 전력이 주어진다.1번팀과 2번팀가 같은 수의 팀원을 가지며 두 팀의 전력차가 최소가 되도록 팀을 배정할 때 각각의 사람이 어떤팀에들어가게 되는지를 구하는 문제다.(만약 두 팀의 전력차가 같은 답이 여러개 있을 경우 사람들의 팀을 순서대로 나열한sequence 가 사전순으로 앞서는 것을 출력. 예를 들어 2 1 1 2 와 2 1 2 1 이 있으면 2 1 1 2 를 출력) 일단 naive 하게 생각해 보면 N이 최대 36이기 때문..