백준 19644 <좀비 떼가 기관총 진지에도 오다니>

투 포인터 문제이다. 즉 윈도 슬라이딩 문제이다.

 

이 문제에서 가장 핵심은 기관통으로 죽일 수 있으면 죽이고 그렇지 않으면 폭탄을 사용하는 문제이다.

 

즉 쏴죽이지 못하거나 폭탄이 없다--> 죽는 상황이다.

 

또한 주의할 점은 폭탄과 기관총 두가지를 동시에 사용할 수 없다는 것이다.

 

문제 풀이

1. 처음 기관총 사격 가능한 범위까지의 Point(몬스터의 위치, 사격 가능 범위)를 queue에 넣는다.
2. 윈도 슬라이딩을 진행하면서 기관총으로 줄일 수 있는지 폭탄으로 죽여야 하는지 판단
3. 폭탄으로 죽일시 다음 몬스터들이 기관총에 안 맞은 횟수를 처리해줄 것

문제를 해결하기 위해 2개의 큐를 사용했다.

 

한 가지는 윈도 슬라이딩을 사용할 큐, 그리고 폭탄으로 죽일 시 기관총 범위 가장 끝의 몬스터 넘버

 

기관총 범위 가장 끝의 몬스터 넘버를 넣는 이유는 이 번호까지는 사격 가능 범위에서 이만큼 제외시켜야 하기 때문이다.

 

처음 상황은 이렇고 사정거리까지 몬스터들을 큐에 담는다.

 

다음 몬스터를 죽이기 위해서는 기관총으로 되지 않기 때문에 폭탄을 사용한다.

 

그렇게 되면 3m까지는 몬스터들의 기관총 맞은 횟수가 1 줄어든다.

그리고 다음 슬라이딩 윈도 역할의 큐는

이상태가 된다. 이러한 흐름으로 진행하면 문제가 풀리게 된다.

 

맨 처음 초기화 부분이다 사정거리가 몬스터 수보다 클 수 있기에 예외처리를 해주었다.

 

몬스터가 기관총으로 죽일 수 있는지 체크하는 부분이다.

 

폭탄이 존재하는 경우 처리해주는 부분이다.

 

생각할 예외 처리가 많은 시뮬레이션 문제였다. 하지만 좋은 문제이므로 추천!

 

전체 코드

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int l, ml, mk, c, result = 1;
	static int num[];
	static Queue<Point> q;
	static Queue<Integer> count;
	static int catchs = -1;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		q = new LinkedList<Point>();
		count = new LinkedList<Integer>();
		l = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		ml = Integer.parseInt(st.nextToken());
		mk = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(br.readLine());
		num = new int[l + 1];
		for (int i = 1; i <= l; i++) {
			num[i] = Integer.parseInt(br.readLine());
		}
		init();// 처음 거리만큼 큐에 담기
		int start = ml + 1;
		while (!q.isEmpty()) {
			if (start <= l) {
				q.add(new Point(start, q.size()));
			}
			Point next = q.remove();
			boolean flag = false;
			if (catchs == -1) {
				if (next.y * mk >= num[next.x]) {
					start++;
					continue;
				}
			} else {
				if ((next.y - (count.size() + 1)) * mk >= num[next.x]) {
					start++;
					continue;
				}
				if(next.x==catchs) {
					if(!count.isEmpty()) {
						next.x=-1;
					}
					else {
						next.x=count.remove();
					}
				}
			}
			if (c > 0) {
				c--;
				if (catchs == -1) {
					catchs = start;
				} else {
					count.add(start);
				}
			} else {
				result = -1;
				break;
			}
			start++;
		}
		if (result == -1) {
			System.out.println("NO");
		} else {
			System.out.println("YES");
		}
	}
	private static void init() {
		// TODO Auto-generated method stub
		for (int i = 1; i <= ml; i++) {
			if (i > l) {// 앞쪽거리보다 유효사거리가 더클 수도 있다.
				return;
			}
			q.add(new Point(i, i));
		}
	}
}