이동식 저장소

1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 문제가 조금 난해하게 쓰여 있지만, 사실 ``최장 경로`` 문제이다. 즉 최장 경로의 길이를 구하고, 최장 경로에 포함되는 간선의 수를 구하는 문제이다. 더보기 # 맞왜틀 1 (펼치기) 최장 경로가 여러 개 있을 경우, 각 경로가 포함하는 간선을 모두 세어야 한다. 예를 들어 다음과 같은 경우가 있다. # 입력 4 6 1 2 1 2 3 2 1 3 3 1 3 3 1 4 2 4 3 1 1 3 # 출력 3 6 일반적인 그래프에서의 최장 경로..

작년에 봤을 때 어려워 보여서 스킵했던 문제이다. 기말고사로 스터디 쉬는 동안 풀어보려고 다시 붙잡았는데, 예상 외로 오래 걸렸다. 한 2주 넘게 생각한듯. 내가 이런 문제에 취약한 건가, 겨우 골드5인데.. 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 이분 탐색이라는 생각이 들긴 했다. 개똥벌레가 높은 구간을 지날수록 파괴해야 하는 석순의 개수는 (일반적으로) 감소한다. 하지만 높은 구간을 지나는 개똥벌레는 (일반적으로) 더 많은 종유석을 파괴해야 한다. 따라서 개똥벌레가 $i$번째 구간으로 지나갈 때 파괴..

3000번: 직각 삼각형 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 점의 좌표가 X Y 순서대로 주어진다. (1 ≤ X,Y ≤ 100,000) 겹치는 점은 없다. www.acmicpc.net 아주 단순한 $O(N^{2}\log N)$짜리 풀이법을 생각할 수 있다. 빗변을 이루는 두 점을 고르고, 직각삼각형이 되기 위해 필요한 나머지 한 점이 존재하는지 찾으면 된다. 두 점을 고르는 데 $N^{2}$, 나머지 한 점을 찾는 데 $\log N$ 시간이 걸린다. 그러나 $N \le 100,000$이므로 이 풀이를 사용하면 시간 초과. 따라서 조금 더 빠른 풀이를 생각해야 한다. 사실 나도 꽤 오래 걸렸다. ``빗변이 아닌 두 변이 좌표축에 평행해야 한다``는..

오랜만에 문제 풀이를 쓴다. 요즘 바빠서;; 2610번: 회의준비 첫째 중에 회의에 참석하는 사람의 수 N이 주어진다. 참석자들은 1부터 N까지의 자연수로 표현되며 회의에 참석하는 인원은 100 이하이다. 둘째 줄에는 서로 알고 있는 관계의 수 M이 주어진다. 이 www.acmicpc.net 위원회 구성 우선 위원회를 구성해야 한다. 서로 알고 있는 사람은 반드시 같은 위원회에 속해야 하므로, Union-Find를 이용하여 위원회를 구성할 수 있다. 서로 알고 있는 사람끼리 ``merge``한 다음, 각 참석자 ``i``를 ``root(i)`` 쪽으로 모은다. 대표 결정하기 대표를 결정하려면 우선 두 사람 사이의 의사전달시간을 알아야 한다. 매번 BFS 등으로 탐색하면 매우 비효율적이므로, 플로이드-와샬..

10253번: 헨리 입력 데이터는 표준입력을 사용한다. 입력은 T 개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 개수 T 가 정수로 주어진다. 각 테스트 데이터는 한 줄로 구성되며, 여기 www.acmicpc.net 뭔가 흥미로운 수학 이야기가 있다. 문제에서 시키는 대로 구현하면 된다. 단, 아주 나이브하게 이중 반복문으로 구현하면 시간 초과가 난다. 다음의 세 가지를 고려해야 한다. 1. $\frac{1}{x} \le \frac{a}{b}$인 최대의 $\frac{1}{x}$ 찾기 부동 소수점 연산을 피하기 위해 수식을 $b \le ax$로 바꾸자. 조건을 만족하는 가장 큰 $\frac{1}{x}$를 찾으려면 가장 작은 $x$를 찾으면 된다. 물론 $x=b$부터 시작하여 조건을..