BOJ 28451 모기 킬러

여러 개의 그리디를 조합하여 푸는 문제입니다.

먼저, 여러 마리의 모기가 같은 칸에 있으면 체력이 가장 높은 모기만 고려하면 됩니다. 그리고 R동으로 후퇴하는 것은 모기가 다가오면 더 좋은 상황이 될 수 없으므로 선택지에서 제외합니다.

모든 모기가 한 칸 다가오는 것은 하얔이가 한 칸 전진하고 T동이 한 칸 멀어지는 것으로 바꿀 수 있습니다.

이제 언제 스프레이를 뿌리고 언제 전진할지를 골라야 합니다. 당장 전진하더라도 모든 모기를 죽일 수 있다면, 당장 스프레이를 뿌리는 것보다 전진해서 스프레이를 뿌리는 것이 더 많은 모기를 공격할 수 있으므로 이득입니다. 당장 전진했을 때 상황이 바뀌는 모기의 범위는 하얔이의 위치 +1에서 +a+1까지입니다. +1과 +2에는 모기가 있으면 안되고, 나머지 자리에 있는 모기들은 이동 뒤에 남은 거리만큼 공격했을 때 죽일 수 있어야 합니다. (+a+1인 이유는 하얔이가 전진하고 모기도 전진하면 거리가 a-1이 되어 스프레이를 뿌렸을 때에 비해 추가로 뿌릴 기회가 1 감소하기 때문입니다. 그 뒤부터는 스프레이를 뿌릴 기회가 감소하지 않습니다.)

마지막으로 지문에 모호한 지점이 하나 있는데, $L$이 1이고 죽일 수 없는 모기가 1의 위치에 있을 때 모기를 무시하고 달려가면 T동에 도착한다고 생각할 수 있지만 -1을 출력해야 합니다.