[백준 / BOJ] 19644 좀비 떼가 기관총 진지에도 오다니

문제

출처 : https://www.acmicpc.net/problem/19644

19644번: 좀비 떼가 기관총 진지에도 오다니

기관총 진지에 좀비떼가 다가오고 있다.

 

킬로와 헥토는 기관총과 지뢰를 이용해 좀비를 막아야한다.

기관총은, L의 사거리에 있는 좀비를 모두 K데미지로 공격한다.

지뢰는 1M사거리에 있는 좀비를 제압한다.

 

이때, 킬로와 헥토가 좀비 떼에게서 살아남을수있을지 구하는 문제다.

 

---

풀이

그리디, 투포인터 문제였다.

좀비의 수(진지의 거리)와 유효사거리가 3*10^6 이므로 시뮬레이션으로 풀경우 시간초과를 맞게된다.

 

문제를 풀기위해 좀비의 위치를 기준으로 탐색하지 않고, 킬로와 헥토의 위치를 기준으로 탐색해야했다.

예를들어, 킬로와 헥토가 현재 3M까지 공격했다면, 다음 4M에 있는 좀비가 입는 피해는, 다음과 같다.

 

- min(4M * K, D*K)

 

이런 방식으로 수학적으로 풀어야하는 문제다.

하지만, 여기서, 지뢰공격한 좀비의 수를 총합하여 데미지를 계산해야하는데, 이 부분이 가장 어려웠다. 

일반적인 방법으로 좀비의 수를 총합할경우, TLE가 나올수밖에없다. 따라서, 투 포인터로 좀비의 수를 총합해줬는데, 방법은 다음과 같다.

 

현재 위치를 right,

현재 위치까지 영향을 미치는 유효 사거리를 left~right 라고 하자.

이때, 내가 이번턴에 공격할 right값은, 다음과 같다는것을 알수있다.

 

(right-left+1)*K - (left~right-1 사이에 있는 지뢰로 제압한 좀비의수 * K)

단, 이때, right-left+1은 절대 D를 넘어가면안된다.

주요 소스코드

   private String defense(int left, int right){
       if(right > L) return "YES";
       delQue(left);
       int damage = Math.max(((right-left+1)*K-q.size()*K), K);
       if(zombies[right] > damage){
           q.add(right);
           if(C > 0) C--;
           else return "NO";
       }
       if(right-left+1 < D) return defense(left, right+1);
       return defense(left+1, right+1);
   }

(left~right-1범위를 벗어난 지뢰공격 좀비를 제외해주기위해서 que를 사용했다.)

 

추가로, 문제의 조건을 잘 생각해보면, 지뢰공격을 해야하는 시기?는 쉽게 유추할수있다.

 

- 기관총은 항상 D미터를 한번에 공격하므로 자신이 제압당하기 직전(1M앞에있는 좀비를 제압할수없을때)이 아니라면, 기관총으로 공격해도 손해보는경우는 절대 없다.

 

따라서, 그리디적으로 자신이 제압당하기 직전(1M앞에있는 좀비를 제압할수없을때)에 지뢰가 남아있다면, 지뢰로 좀비를 공격하고, 지뢰공격이 불가능하다면 "NO"를 출력하면된다.

 

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/BOJ%20source%20code/19644%20%EC%A2%80%EB%B9%84%20%EB%96%BC%EA%B0%80%20%EA%B8%B0%EA%B4%80%EC%B4%9D%20%EC%A7%84%EC%A7%80%EC%97%90%EB%8F%84%20%EC%98%A4%EB%8B%A4%EB%8B%88/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃