- boj 16389 ac, 다4
스케쥴링 문제로 생각하면 된다. h를 기준으로 오름차순 정렬 후, h-t가 현재 수위 이상이라면 가고, 그렇지 않다면 지금까지 갔던 지점들 중 t값이 가장 큰 지점에 대하여 수위를 낮추면서 방문한 지점 갯수를 유지할 수 있다면 방문하면 된다. 개인적으로는 플1 정도의 난이도라고 생각한다.
//반례
5
3 5
3 6
1 7
2 8
4 10
//Wrong Answer: 3
//Answer: 4
- boj 15773 ac, 다4
16389와 비슷한 문제이다. 16389를 풀고 이 문제를 접해서 스케쥴링 문제인것은 바로 알아챘지만, 그럼에도 데드라인을 구하고 어떤것을 기준으로 잡아 그리디하게 풀어야 할지 고민을 많이 했던 문제였다. 결론적으로는 l+d 값을 기준으로 오름차순 정렬 후 16389와 같이 풀면 되는데, 직관적으로 보면 d값을 기준으로 잡아야 할 것만 같아 보인다. 그러나 16389와는 달리 고도가 l보다 높아지면 그 풍선을 불 수 없기 때문에 여기선 어떤 풍선을 먼저 부는지가 중요하다. 두 풍선 b1과 b2에 대해 b1이 b2보다 우선순위가 높아지기 위해선 b2를 먼저 불면 b1을 불 수 없고, b1을 먼저 불면 b2도 불 수 있는 상황이여야 한다. 이는 b1의 l값과 d값 모두 b2의 l값과 d값보다 같거나 커야한다는 의미이고, 따라서 l+d를 기준으로 오름차순 정렬 후 풀어야 하는 것이다.
