[UVa 10382 ] Watering Grass

https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=1323 

Online Judge

 

 

# problem

가로가 L미터이고 폭이 W미터인 잔디밭에 n개(최대 10000개)의 스프링 쿨러가 설치되어 있다.

각 스프링 쿨러는 잔디밭의 세로로 가운데 지점에 설치되어 있으며, 일정한 작업 반경 R을 가지고 있다고 할 때.

잔디밭 전체에 물을 주기 위한 스프링 쿨러의 최소 개수는?

 

 

 

# 스프링 쿨러마다 다른 작업 반경 R.

idea ) 지름으로 생각하지 않고, 구간으로 파악을 한다면 interval covering 문제로 생각할 수 있다

== 스프링 쿨러를 1차원 interval로 표현할 수 있다.

== 잔디밭의 길이 L을 모두 커버하기 위한 interval의 수를 구하는 문제와 동일.

==> GREEDY!

 

=> 위의 작업을 통해 [1,L]을 커버할 수 있는 interval의 최ㅗ소 개수를 구하는 문제로 변경되었다.

 

Interval을 leftmost increasing, rightmost deacresing으로 정렬 한 후 greedy하게 맨 왼쪽 interval붙 배정을 한다.

 

 

이 경우 "L x W" 에 대한 greedy optional solution은 반드시 (L-1) x W에 대한 greedy optional solution을 가지고 있다.

 

이 또한 증명을 해야 하는데

감히 인간 감자 그 언저리 나부랭이인 내가 천재적이고 전지전능하신 교수님의 말씀을 대충 빌리자면

귀류를 통하여 증명을 할 때, interval 정렬 기준에서 어긋나기 때문에 무조건 위의 명제가 성립한다고 한다.

 

 

 

 

이정도면 증명이 됐겠지...?

ㅋㅋㅋㅋㅋㅋㅋㅋㅋ

이렇게 interver covering으로 진행을 하면 Sorting으로 문제를 해결하는 것 이기 때문에 nlogn 시간이 걸린다.

아이고 디다.