이동식 저장소

오랜만에 골드 탐험 ㅎㅎ 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 크기가 각각 $a$와 $b$인 카드 묶음을 합치려면 카드를 $a+b$번 비교해야 한다. 카드 묶음의 크기가 주어질 때, 카드 묶음을 하나로 합치려면 카드를 최소 몇 번 비교해야 하는지 구해 보자. 직접 해 보기 크기가 각각 $a$, $b$, $c$인 세 개의 카드 묶음을 합쳐 보자. 먼저 $a$와 $b$를 합치고, 그 후에 $c$를 합친다면 비교 횟수는 몇 번인가? 일단 $N$개의 카드 묶음을 하나로 합치려면 묶음을 $N-..

오래 전부터 알고만 있던 문제. 3653번: 영화 수집 각 테스트 케이스에 대해서 한 줄에 m개의 정수를 출력해야 한다. i번째 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있었던 DVD의 개수이다. 상근이는 매번 영화를 볼 때마다 본 영화 DVD www.acmicpc.net 영화의 위치를 추적하는 문제이다. $N$과 $M$이 각각 최대 10만이므로 로그 시간 안에 위치를 찾고 업데이트해야 한다. 쿼리를 로그 시간에 수행하는 방법은 여러 가지이지만, 알고 있는 모든 방법을 검토해 보니 세그먼트 트리가 적당해 보인다. 그 중에서도 합 세그먼트 트리를 써 보자. 트리에 무엇을 저장할까? 위치를 직접 저장할 수는 없고, 특정 위치에 DVD가 있는지 저장하면 될 것 같다. 이렇게 하면 특정 DVD 앞에..

플래티넘 재활중. 물론 쉽지 않다... 13141번: Ignition 첫 번째 줄에는 그래프의 정점의 수 N과 간선의 수 M이 주어진다. (2 ≤ N ≤ 200, N-1 ≤ M ≤ 20,000) 두 번째 줄부터 M개의 줄에는 각 간선의 시작점 S, 끝점 E, 길이 L이 주어진다. (1 ≤ L ≤ 100) 시작점 www.acmicpc.net 정점 중 하나에 불을 붙여 그래프를 태울 때, 그래프가 다 타는 시간의 최솟값을 구해야 한다. 일단 지문에서 파악할 수 있는 내용은 그래프가 다 타는 최소 시간을 구하기만 하면 된다. 불은 1초에 거리 1씩 간선을 태운다. 간선의 양 끝에 불이 붙는 경우, 불이 간선의 어느 지점에서 만날 때 불이 꺼진다. 불이 정점에 도달하면 정점에 연결된 모든 정점에 즉시 불이 붙는..

요즘 플레 공부하는 중. 나름 3시간정도 고민해 봤지만, 플레3을 내 실력으로 풀 수 없으므로(......) 답 보고 공부한 내용을 올린다. 9938번: 방 청소 처음 6개의 술은 규칙 1에 의해서 1, 3, 5, 7, 9, 2번 서랍에 보관할 수 있다. 7번째 술은 규칙 3을 적용할 수 있다. 1번 서랍에 들어있는 술을 2로, 2번 서랍에 들어있는 술을 3으로, 3번 서랍에 들어있 www.acmicpc.net 어린이날을 맞아 바닥에 어질러진 술병을 서랍에 넣으려 한다. 각 술병은 서랍 두 곳 중 하나에 들어갈 수 있다. 문제에서 주어진 규칙대로 술병을 넣을 때, 각 술병을 넣을 수 있는지 구하는 문제이다. 엥 이거 완전 이분 매칭 아니냐? 아니다 정점이 더 많은 집합의 정점이 $V$개이고 간선이 $E$..

어제 union find 공부한 게 기억에 남아서, 대충 비슷해 보이는 문제를 풀기로 했다. 17616번: 등수 찾기 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 세 정수 N, M, X가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 105, 1 ≤ M ≤ min(N(N-1)/2, 5×105), 1 ≤ X ≤ N) . 다음 M 줄에는 각각 두 정수 A, B가 주어 www.acmicpc.net 두 학생의 상대적인 순위를 비교한 데이터가 주어질 때, 학생 $x$의 순위가 될 수 있는 최고/최저 순위를 구하는 문제이다. 어제 공부한 union find 업데이트를 적용해 보자. 등수가 가장 높은 학생을 루트로 하는 집합이 있을 때, $x$보다 순위가 높은 학생을 $above[x]$라고 정의하자. $abo..