BOJ 5910 - Mountain Climbing

역시 우사코 문제는 정말 좋은 것 같다.

 

그리디 문제가 다 그렇듯(?) 아이디어 떠올리는 것은 좀 힘들었다.

---

체감 티어: P2

태그: greedy, sorting

우선 한번 단순하게 생각해 보자.

일단 올라가는 속도가 빠른 소부터 보낸다고 생각한다면 아주 틀린 것은 아니다.

 

하지만 만약 내려가는 소가 있지만 올라오는 소의 속도가 더 느리다면 내려가는 소가 다 내려간 후 공백이 생긴다.

이 내용을 토대로 생각해 보자, 올라오는 소와 관계없이 내려가는 소가 계속 존재한다면 시간 이득을 볼 수 있다.

이미 올라간 소가 내려올 때 올라오는 소의 속도가 더 느리면 결국엔 이 구간에서 총 걸리는 시간은 올라오는 소의 것이 된다.

결국 이 말은 내려오는 소의 속도가 느린 만큼 더 많은 소가 올라와서 정상에 대기할 수 있다는 말이 된다.

up<=down인 소들이 먼저 산을 올라가는 것이 더 효율적일 것이다.

 

up<=down인 소들은 up을 기준으로 오름차순, up>down인 소들은 down을 기준으로 내림차순으로 정렬해 준다.

그 이유는 어차피 up<=down인 소들은 산 정상에서 내려올 때 손해를 최소한으로 할 수 있는 소들이고 up>down인 소들은 down이 큰 순으로 소들을 보내준다면 다음 소들이 올라올 수 있는 시간을 만들어 줄 수 있기 때문이다.

 

그래서 이걸 한마디로 말하자면 그냥 농부 FD를 쉴 틈 없게 해주면 된다는 말인 것이다.

 

정상에 올라간 모든 소들이 내려가는데 걸리는 시간을 top이라고 하자,

만약 top<=U(i)라면, 내려가는 소들이 걸리는 시간보다 올라오는 데 걸리는 시간이 더 김으로 총 걸리는 시간+U(i)가 되고 top=D(i)로 바꿀 수 있다..

top>U(i)라면, 총걸리는 시간+ U(i)가 되고 top의 값은 top-U(i)+D(i)꼴로 볼 수 있다.