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

2026년 4월 28일에 백준 사이트가 서비스 종료되므로 문제 링크 미첨부

문제 정의

정의

• 좀비는 $1m$씩 진지로 접근
• 기관총은 현재 사격 시점으로부터
  $[1, M_L]$ 범위에 있는 모든 좀비에게 $M_K$ 대미지
• 지뢰는 진지 앞 $1m$에 도달한 좀비를 즉사시키지만,
  사용 시 해당 턴에는 기관총을 쏠 수 없다.
• 진지 앞 $1m$에서 좀비를 처치하지 못하면 패배NO
• 모든 좀비를 처치하면 승리YES

출력

1. 길의 거리: $L (1 ≤ L ≤ 3,000,000)$
2. 기관총 사거리 $M_L (1 ≤ M_L ≤ 3,000,000)$
   공격력 $M_K (1 ≤ M_K ≤ 100)$
3. 지뢰 개수: $C_{ammo} (0 ≤ C_{ammo} ≤ 3,000,000)$
4. 좀비 체력: $L$개의 줄에 걸쳐
   각 위치 $i$(1 ~ L)의 좀비 체력 $Z_i (0 ≤ Z_i ≤ 300,000,000)$

---

예시 입출력

예제 1)

입력

6
3 2
2
3
4
6
6
6
6

출력

NO

예제 2)

입력

6
3 2
1
2
4
6
6
6
8

출력

YES

---

접근 방법

1. 큐를 이용한 대미지 범위 관리

기관총은 매 미터 쏠 수 있지만, 지뢰를 사용한 턴에는 쏠 수 없습니다.

큐의 크기(q.size())는 현재 좀비의 위치에서 기관총 대미지를 방해하는 지뢰 사용 횟수를 의미합니다.

q.peekFirst() < i 조건은 해당 지점에서 사용했던 지뢰의 영향(기관총 사격 불가 범위)이 현재 위치 i를 벗어났음을 의미하므로 큐에서 제거합니다.

2. 현재 좀비가 받는 대미지 계산

int damage = (Math.min(ml, i) - q.size()) * mk;

• Math.min(ml, i):
  좀비가 $i$미터 지점에서 $1$미터 지점까지 오면서
  받을 수 있는 최대 사격 횟수입니다.
  (사거리 $ml$보다 멀리 있다면 최대 $ml$번, 가깝다면 $i$번)

• 여기에 q.size()를 빼줌으로써
  지뢰를 쓰느라 총을 쏘지 못한 횟수를 제외한 실제 타격 횟수를 구하고 공격력 $m_k$를 곱합니다.

3. 그리디(Greedy) 판단

z > damage:
계산된 대미지로 좀비를 죽일 수 없다면
이 좀비는 반드시 지뢰로 처리해야 합니다.

지뢰를 사용하면 $C$를 $1$ 감소시키고, 큐에 $i + ml - 1$을 넣습니다.
이는 현재 위치에서 쏜 지뢰 때문에
향후 사거리 $ml$ 동안은 기관총 사격 횟수가 1회씩 손실됨을 기록하는 것입니다.

만약 지뢰가 부족$(C < 0)$하다면 즉시 NO를 반환합니다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class Main {
    static StringTokenizer st;
    public static void main(String[] args) throws IOException {
        System.out.println(greedy());
    }

    private static String greedy() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int L = Integer.parseInt(br.readLine());

        st = new StringTokenizer(br.readLine());
        int ml = Integer.parseInt(st.nextToken());
        int mk = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(br.readLine());


        ArrayDeque<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= L; i++) {
            if (!q.isEmpty() && q.peekFirst() < i) q.poll();

            int z = Integer.parseInt(br.readLine());
            int damage = (Math.min(ml, i) - q.size()) * mk;

            if (z > damage) {
                if (--C < 0) return "NO";
                q.offer(i+ml-1);
            }
        }

        return "YES";
    }
}