2/7

- 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$보다 높아지면 그 풍선을 불 수 없기 때문에 여기선 어떤 풍선을 먼저 부는지가 중요하다. 두 풍선 $b_1$과 $b_2$에 대해 $b_1$이 $b_2$보다 우선순위가 높아지기 위해선 $b_2$를 먼저 불면 $b_1$을 불 수 없고, $b_1$을 먼저 불면 $b_2$도 불 수 있는 상황이어야 한다. 이는 $b_1$의 $l$값과 $d$값 모두 $b_2$의 $l$값과 $d$값보다 같거나 작아야 한다는 의미이고, 따라서 $l + d$를 기준으로 오름차순 정렬 후 풀어야 하는 것이다.