Link https://www.acmicpc.net/problem/16074 GCPC 2018 M번 Tag PBS Time Complexity $O((N+Q)lgN)$ 가중치가 있는 $N \times M$ 그리드가 있고, $(x1, y1)$ 와 $(x2, y2)$ 를 잇는 경로의 가중치의 최댓값의 최솟값을 묻는 쿼리가 Q개 주어진다. 쿼리 하나를 이분탐색으로 처리한다고 생각해보면, '가중치가 $k$ 이하인 정점들만 가지고 $(x1, y1)$ 와 $(x2, y2)$ 를 연결할 수 있는가?' 가 결정문제가 되고, 이는 Union-Find 를 이용해주면 된다. Q개의 쿼리를 처리하려면, 가중치가 작은 정점부터 보면서 추가하고 해당 mid값을 가진 쿼리에 대해 답해주면 된다. PBS 연습문제. Code
Link https://www.acmicpc.net/problem/18251 Good Bye, BOJ 2019! E번 Tag 완전탐색 Time Complexity $O(Nlg^{2}N)$ 각 정점에 가중치가 있는 포화이진트리를 평면에 그려서 x, y축에 평행한 임의의 직사각형 내부 가중치의 합을 최대화해야한다. 금광 하위호환...? 그냥 완전탐색 하면 된다. 포화이진트리에 노드가 $N$개면 높이가 $lgN$이고, 이는 직사각형의 위아래가 될 수 있는 경우의 수가 $lg^{2}N$ 밖에 없음을 의미한다. 이 모든 후보에 대해 $O(N)$에 최대 연속합을 구해주면 된다. Code
4.2 ~ 4.11 동안 푼 문제 정리 산만한 고양이 https://www.acmicpc.net/problem/14866 DFS 스패닝 트리를 만들고 Tree DP 느낌으로 서브트리 내부의 Back Edge들을 잘 카운트하고 케이스 분류하면 각 정점의 자식들을 확인하면서 사이클을 제거할 수 있는지 판단 가능하다. The Bridege on the River Kawaii https://www.acmicpc.net/problem/16695 처음 보면 좀 무서운데, $V
Link https://www.acmicpc.net/problem/10129 POI 2013/2014 Stage 2 3번 Tag dp Time Complexity $O(QN)$ $N$개 나무의 높이가 주어지고, $Q$마리의 새가 1번 나무에서 N번 나무까지 날아간다. 각 새는 한번에 $k_{i}$ 그루의 나무만큼 날아갈 수 있고, 현재 위치한 나무보다 높이가 같거나 높은 나무로 날아갈때 피로감을 느낀다. 각 새의 피로감 느끼는 횟수를 최소화해야한다. 쿼리가 있긴 한데 $Q \le 25$이라 그냥 따로따로 풀어도 상관없다. dp 점화식은 쉽게 나온다. $dp[i]=min(dp[j]+C)$ $(i-k \le j < i)$ ($C$는 $h[j] \le h[i]$일때 1, 아니면 0) 모든 j에 대해 고려하면 ..
Link http://codeforces.com/contest/1332/problem/E Codeforces Round #630 (Div. 2) E번 Tag 수학 Time Complexity $O(lg(NM))$ 인접한 두칸을 골라 1씩 증가시키거나 한칸을 골라 2씩 증가시키는 연산을 할 수 있을 때, 모든 칸의 숫자를 같게 만들 수 있는, 각각의 수는 $L$ 이상 $R$ 이하이고 $N \times M$ 크기 격자의 갯수를 구해야 한다. 몇가지 관찰을 통해 해결할 수 있다. 먼저, 한칸을 골라 2씩 증가시키는 연산이 존재하기 때문에 각 칸의 홀짝성만이 중요하다. 두번째, 임의의 두 칸의 홀짝성을 바꿀 수 있다. 두 칸 사이의 경로에다가 인접한 두칸을 골라 1씩 증가시키면 경로상에서 두 칸의 홀짝성은 반전..
Link https://atcoder.jp/contest/abc159/tasks/abc159_f AtCoder Beginner Contest 159 F Tag dp Time Complexity $O(NS)$ 길이 N인 수열과 정수 S가 주어진다. $f(L, R)$ 은 수열에서 L이상 R이하 인덱스로 만들수 있는 합이 S인 부분집합의 갯수로 정의된다. 이때 모든 $(L, R)$ 쌍에 대해 $f(L, R)$의 합을 구해야 한다. 일단 $L = 1$로 고정했다고 생각해보자. $dp[i][j]$ := (1 ~ i)까지 선택해서 합이 j가 되는 경우의 수 로 정의하면, 냅색처럼 $O(NS)$에 dp 배열을 채울 수 있다. 이때 초기값으로 $dp[i][0] = 1$로 했을 것이다. $L = 2, 3, ... , R..
Link https://www.acmicpc.net/problem/14164 USACO 2016 December Platinum 1번 Tag 기하 Time Complexity $O(N^{3})$ 점 N개가 있고, 이 중 3개를 택해 삼각형을 만들때 내부에 점이 i개 (0≤i≤N-3) 있는 삼각형의 갯수를 구해야 한다. $O(N^{2})$ 개의 선분에 대해 왼쪽에 있는 점의 갯수를 ccw를 이용해 각각 $O(N)$, 총 $O(N^{3})$에 전처리한다. cnt[i][j] = 선분 ij 왼쪽에 있는 점의 갯수 라고 하면, 삼각형 ABC 내부의 점의 갯수는 cnt[A][B], cnt[B][C], cnt[A][C]로 나타 낼 수 있다. 따라서 $O(N^{3})$ 개의 삼각형에 대해 내부의 점 갯수를 $O(1)$..
Link https://www.acmicpc.net/problem/2452 KOI 2011 전국본선 중/고등부 4번 Tag bfs Time Complexity $O(N^{2}M^{2})$ 흰색/검은색 돌로 구성된 $N*M$ 격자가 주어진다. 어떤 돌을 선택해 뒤집으면 같은 색으로 연결된 컴포넌트들이 전부 뒤집힌다. 전체 격자를 같은 색으로 바꾸기 위해 필요한 최소한의 뒤집기 횟수를 구해야 한다. 가장 중요한 관찰은, '처음 뒤집은 돌을 계속 뒤집어도 된다'는 것이다. 따라서 $N*M$개의 돌을 모두 시도해 보면서, 그 돌만 눌렀을때 총 몇번 뒤집어야 하는지 계산하면 된다. 인접한 돌들끼리 간선을 연결하고, 같은 색끼리는 0, 색이 다르면 1의 가중치를 가지는 그래프를 생각해 보자. 이때 $(sx, sy)..