IOI 2011 Elephants https://www.acmicpc.net/problem/5823https://oj.uz/problem/view/IOI11_elephants $O(N^{1.5})$ 풀이는 다른 블로그 등에서 찾아볼 수 있다. $N$개의 점을 길이 $L$의 구간으로 덮을 때 최소 몇 개가 필요한지 묻는 문제이다. 이런 문제를 풀 때 먼저 할 수 있는 생각은 그래프 문제로 변환하는 것이다. 점이 $x$ 위치에 있다면, $x$에 검은 점을 두고 $x+L+1$에 흰 점을 두고 검은 점에서 흰 점으로 길이 1의 간선을 잇자. 그리고 모든 흰 점에서 자신의 직후에 있는 점으로 향하는 길이 0의 간선을 잇자. 이제 구하는 답은 가장 왼쪽의 점에서 가장 오른쪽 점까지 가는 최단거리가 된다. 모든 점에서 나오는 간선이 한 개 이하이며,.. 더보기 이전 1 2 3 4 ··· 24 다음