BOJ 21792. Meetings 2 먼저 답 후보가 여러 개인 경우가 언제 일어나는지 살펴 봅시다. $2i$명의 비버가 만난다고 할 때, 답 후보가 $j$개인 참석자 선정이 존재한다면 트리에 아래 조건을 만족하는 경로가 존재합니다. 경로의 길이는 $j-1$이고, 경로의 양쪽 서브트리(경로의 양 끝점 포함)에 정점이 각각 $i$개 이상 존재한다. 같은 맥락으로 만약 참석자 수가 홀수라면 답은 항상 1개입니다. Subtask 2 (20점) $O(N^2)$ 풀이가 가능하므로, 가능한 모든 경로에 대해 양쪽 서브트리에 있는 정점 개수를 적당한 전처리를 통해 $O(1)$에 찾아주면 됩니다. 자세한 설명은 생략합니다. Subtask 3 (100점) 가능한 모든 경로를 시도해 봐야 하는데, $N$이 큰 경우 사용..
BOJ 4008. 특공대 $$S_i = \sum_{1 \le j \le i} A_j $$ $$DP[i] = \max_{0 \le j < i} \left( a(S_i - S_j)^2 + b(S_i - S_j) + c + DP[j] \right)$$ 이제 위 점화식을 빠르게 계산해 봅시다. $$ \begin{align} DP[i] &= \max_{0 \le j < i} \left( aS_i^2 - 2aS_i S_j + aS_j^2 + bS_i - bS_j + c + DP[j] \right) \\ &= aS_i^2 + bS_i + c + \max_{0 \le j < i} \left( -2aS_i S_j + aS_j^2 - bS_j + DP[j] \right) \end{align}$$ 위 식은 CHT의 전형적인..
BOJ 14636. Money for Nothing 문제는 $\max_{1 \le i \le m} \max_{1 \le j \le n} (q_j - p_i) (e_j - d_i)$를 구하는 것입니다. 식의 형태가 직사각형의 넓이를 구하는 것과 닮았기 때문에, $(p_i, d_i)$, $(q_j, e_j)$ 상에 플로팅한 기하 문제로 바꿔 봅시다. 모든 점 쌍을 시도해 보기에는 시간이 너무 오래 걸립니다. 여기서 관찰해야 할 사실 하나는 [절대로 답에 포함될 수 없는 점]이 존재한다는 것입니다. 예를 들어, $(p_i, d_i)$가 $(p_j, d_j)$보다 오른쪽 위에 있다면 $(p_i, d_i)$는 절대 답에 포함될 수 없습니다. 또한 어떤 $(q_i, e_i)$에 대해서도 이득을 볼 수 없는 $(p_..
BOJ 22031. Yet Another Interval Graph Problem 먼저 구간들을 끝점 순서대로 정렬합시다. 즉 $i < j$이면 $e_i \le e_j$입니다. $DP[i]$를 $i$번 구간이 선택된 가장 번호가 큰 구간일 때의 답으로 정의합시다. 이때 $j < i$인 $j$에 대해 $DP[j]$에서 $DP[i]$의 상태 전이를 빠르게 구할 수 있으면 문제를 $O(N^2)$ 남짓한 시간 복잡도에 풀 수 있습니다. $DP[j]$에서 $DP[i]$로 전이하는 방법을 찾아봅시다. 이는 곧 $[j+1, i]$ 인덱스를 가진 범위 중 $K$개 이하를 잘 선택해 최대 가중치를 가진 연결 성분을 구하는 것과 같은데, $DP[j]$의 정의상 $j$번 범위를 이미 선택했으므로 다음 연결 성분의 범위들은 ..
BOJ 7644. Highway Construction 트리 DP를 돌려 주며, 각 점이 경로의 LCA일 때의 답을 구해 주면 됩니다. 먼저 각 점에서 아래로 가장 먼 점까지의 거리를 전처리해 주고, 이것을 이용해 트리 DP를 할 수 있습니다. 어떤 점 $v$의 자식 $c$를 봅시다. $v$를 LCA라고 하면, 자식 최대 두 개를 골라 해당 자식을 경로에 포함시킬 수 있습니다. 경로에 포함되지 않는 자식의 경우 해당 서브트리에서 가장 먼 정점까지의 거리만이 중요하고, 경로에 포함되는 자식의 경우 트리 DP를 통해 올려준 값이 중요합니다. 해당 값들로 LCA가 $v$일 때의 답을 구한 후, 이번에는 자식을 하나만 골랐을 때의 답을 부모로 전달해 줍니다. 더보기 #include using namespace ..
BOJ 20641. Sleeping Cows 문제에서 요구하는 조건은 크게 두 가지입니다. 모든 소가 하나의 헛간에 들어갈 수 있도록 선택할 것 선택하지 않은 소들은 모두 선택하지 않은 헛간보다 크기가 클 것 2번 조건을 다른 말로 표현하면, "선택하지 않은 가장 작은 소"가 "선택하지 않은 가장 큰 헛간"보다 크면 됩니다. 따라서 선택하지 않은 가장 작은 소를 고정하고, 2차원 DP를 돌리면 $O(N^3)$ 풀이가 나옵니다. DP에 대해 간단히 설명하면 우선 헛간과 소를 모두 한 배열에 넣고 크기 순으로 정렬한 뒤, 왼쪽부터 차례로 보면서 그 인덱스를 i, (지금까지 선택한 소의 수 - 지금까지 선택한 헛간의 수)를 j로 정의하면 됩니다. 이제 $N$을 하나 떼어 봅시다. 선택하지 않은 가장 작은 소의..
지인 분들에게 추천받은 문제들을 풀어 보았습니다. BOJ 12963. 달리기 번호가 큰 간선부터 보면서, 해당 간선 용량만큼의 사람을 추가로 보낼 수 있는지 판별합시다. 이때 남은 간선들을 통해 시작점에서 끝점까지 모든 간선의 용량이 $3^i$ 이상인 경로를 만들어야 합니다. 이러한 경로가 존재하지 않으면 사람을 보낼 수 없습니다. $3^0 + 3^1 + \cdots + 3^i < 3^{i+1}$이기 때문에, 용량이 큰 간선을 직접 사용하지 않는 이상 용량이 더 작은 간선들에 의해 막히는 일이 없습니다. 따라서 용량 큰 간선을 최대한 취하는 것이 최적 전략이고, Union Find 자료구조를 이용해 시작점에서 끝점까지 경로가 존재하는지 판단해 주면 됩니다. 나이브하게 짤 경우 $O(NM)$, Union ..
https://www.acmicpc.net/problem/7469 7469번: K번째 수 현정이는 자료 구조 프로젝트를 하고 있다. 다른 학생들은 프로젝트 주제로 스택, 큐와 같은 기본 자료 구조를 구현하는 주제를 선택했다. 하지만, 현정이는 새로운 자료 구조를 만들었다. 현정 www.acmicpc.net Step 1 ($O(M \log^3 N)$) 이 단계는 머지 소트 트리를 알고 있다면 누구나 풀 수 있습니다. 머지 소트 트리는 일반적인 세그먼트 트리와 비슷한데, $[l, r]$ 구간을 담당하는 노드에는 $[l, r]$ 구간에 있는 수들을 정렬해서 배열 형태로 저장해 둔 세그먼트 트리를 말합니다. 머지 소트 트리의 구축은 모든 노드에 대해 정렬을 독립적으로 하면 $O(N \log^2 N)$에 가능합니..