문제 백준 1939번 풀이 옮길 수 있는 물건의 중량은 이어진 다리의 가중치 중 최솟값이 됩니다. 그러므로 가중치가 큰 간선(다리)을 이어주면서 공장끼리 이동 가능한지 확인하면 됩니다. 이 과정은 유사 크루스칼 알고리즘(Union-Find)을 돌리는 것으로 해결할 수 있습니다. 소스코드 #include #define all(v) v.begin(), v.end() using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pii; typedef pair pll; typedef vector vi; typedef vector vl; typedef vector vpii; typedef vector vpll; typ..

문제 백준 2170번 풀이 수직선 상에 테스트 케이스를 나타내봅시다. 현재 선이 그이고 있는가? 그이지 않고 있는가?를 생각해보며 문제를 풀어주면 쉽게 풀 수 있습니다. 선이 그이고 있는가 없는가 는 긋기 시작하면 1을 증가시켜주고, 긋는 것을 멈출 때 1 감소시켜주는 변수 하나로 관리할 수 있습니다. 주석으로 설명을 대체합니다. 소스코드 #include #define all(v) v.begin(), v.end() using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pii; typedef pair pll; typedef vector vi; typedef vector vl; int main() { io..

문제 백준 4913번 풀이 구간에 해당하는 소수를 빠르게 구하기 위해서, 구간 $[1, 100,000,000]$에 해당하는 모든 소수를 에라토스테네스의 체를 사용하여 구해줍니다. 해당 구간에 소수를 순서대로 넣으면, 정렬된 상태이기 때문에 이분 탐색을 사용할 수 있습니다. 문제 입력에서 주어지는 $[L, U]$에서 $upper(U) - lower(L) $한 수가 소수의 개수가 되겠네요. 비슷하게 제곱수의 합으로 나타낼 수 있는 수도 위처럼 구할 수 있습니다. 에라토스테네스의 체로 소수($p$)를 구할 때, $(p-1)mod4 = 0$을 만족하는 경우만 따로 관리해주면서, 위처럼 이분 탐색을 사용하여 풀 수 있습니다. 다만, $1^1 + 1^1 = 2$가 되는 "짝수인 소수 2"를 따로 고려해야 합니다. ..

문제 백준 14621번 풀이 빨간색 파란색을 잇는 간선을 제외하고 모두 제거합니다. 남은 간선을 가지고 정점을 모두 연결시킬 수 있는 MST (최소 스패닝 트리)를 만들면 됩니다. 정렬하는데 $ O(MlogM) $, 연결하는데도 $ O(MlogM) $이 걸리니 시간 복잡도 $O(MlogM)$에 해결할 수 있습니다. MST를 구하는 방법 (백준 1197번, 최소 스패닝 트리(MST)를 구하는 크루스칼 알고리즘) 소스코드 #include #define all(v) v.begin(), v.end() using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pii; typedef pair pll; typedef ..

문제 백준 15918번 풀이 $ x $와 $ y $ 자리가 주어집니다. 문제에서 같은 수는 수열에서 "2번" 나오고, 같은 수 ($ k $) 사이의 원소 개수가 $ k $가 된다고 하였으니, $ x $와 $ y $ 자리에 넣을 수는 $ y - x + 1 $로 정해집니다. 나머지 수를 채우는 방법은 dfs를 사용하여 $ 2^(12) $만큼 돌면서 조건에 맞게 수열을 채워주면 됩니다. 시간 복잡도는 $ O(2^N) $이 됩니다. 소스코드 #include #define all(v) v.begin(), v.end() using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pii; typedef pair pll;..

문제 백준 1644번 풀이 에라토스테네스 체를 사용하여 구간 $[2, N]$ 사이의 모든 소수를 구해줍니다. 구한 소수를 배열에 오름차순으로 두고, 그 배열의 길이를 $ K $로 둡니다. 어떤 구간이 $ N $이 되는지 찾아봅시다. 첫번째로는 누적합을 사용하여 모든 $ i, j (1 \leq i \leq j \leq N) $에 방문하여 $ psum[j] - psum[i] = N$인지 확인해주면 $ O(K^2) $에 가능합니다. 하지만, $ N $의 범위가 $ 4,000,000 $이므로 $ K $가 $ 10,000 $을 넘어가서 제곱 풀이는 사용할 수 없습니다. 누적합에서는 모든 $i, j$를 방문하지만, 투포인터로 가능한 $i, j$만 빠르게 탐색할 수 있습니다. 투포인터의 왼쪽 포인터를 $ L $, 오..