이동식 저장소

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$이므로 이 풀이를 사용하면 시간 초과. 따라서 조금 더 빠른 풀이를 생각해야 한다. 사실 나도 꽤 오래 걸렸다. ``빗변이 아닌 두 변이 좌표축에 평행해야 한다``는..

요즘은 이분 매칭 문제를 풀고 있다. 1574번: 룩 어택 첫째 줄에 체스판의 크기 R과 C가 주어지고, 빈 칸의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 빈 칸의 좌표가 주어진다. 좌표는 (행, 열)의 형태로 주어지고, 가장 윗 행은 1번 행이고, 가장 왼�� www.acmicpc.net $R \times C$ 크기의 체스판에 룩을 최대한 많이 배치하는 문제이다. 이때 룩끼리 공격 가능해서는 안 된다. 룩은 자신이 위치한 행 또는 열의 모든 칸을 공격할 수 있다. 비슷한 문제로 N-Queen이 있다. 이 문제는 $N \times N$의 체스판 위에 퀸을 서로 공격할 수 없도록 최대한 많이 배치하는 문제이다. 퀸은 행과 열에 더하여 대각선까지 공격할 수 있기 때문에 특정한 형태로 모델링하기 까다롭다..

4시간동안 맞왜틀 해서 화나서 쓴다. 9577번: 토렌트 희원이가 사용하는 ACM토렌트는 하나의 파일을 공유받을 때 여러 조각으로 나누어, 조각을 지닌 시드가 접속하는 시간에 시드로 부터 일부 조각을 전송 받아 파일을 완성시키는 방법으로 파일이 www.acmicpc.net 회원들로부터 $n$개의 파일 조각을 다운로드하는 데 걸리는 최소의 시간을 구하는 문제이다. 어떤 파일 조각을 아무 회원으로부터 다운로드해도 되기 때문에, 회원에 대한 정보는 무시하고 파일 조각과 시간의 관계만 생각하자. 전형적인 이분 매칭 문제이다. 매칭하는 방향은 두 가지가 있는데, 나는 조각에 시간을 매칭했다. 각 조각을 다운로드할 시작 시각을 매칭하는데, 이때 시작 시간을 매칭하므로 그래프를 만들 때 $t_{2}$는 제외해야 한다..