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

1. 문제

www.acmicpc.net/problem/19644

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

2. 접근방법

 

기관총과 폭탄을 던져 살아남는 시뮬레이션 문제

 

좀비가 내 눈앞에 왔을때의 체력이 기관총 데미지 보다 높다면 폭탄을 써야하고

폭탄을 써야하는데 폭탄이 없으면 죽는다는 것에 초점을 맞췄다.

 

좀비가 내 눈앞에 도착했을 때 체력을 어떻게 알 수 있을까

 

이렇게 좀비가 가득 차 있을때

기관총 데미지는 10

기관총 사거리는 5라고 가정했을 때 시뮬을 돌려보면

99는 폭탄을 사용한 곳이라 할때 아래 숫자가

내 앞에 좀비가 도달할때까지 기관총으로 줄 수 있는 데미지를 나타낸다.

 

잘 보면 어떠한 규칙이 보이는데

 

바로 알려주면 해당 위치 좀비 앞에 사거리 만큼을 봤을때 기관총 데미지 * 사거리 - (빈칸이거나 폭탄으로 죽인 숫자)*기관총 데미지 가 된다.

사각형으로 보면 30을 구하는 법은 총데미지 10*5 = 50에서 빈칸 2 자리 10*2 = 20 을 뺀 50 - 20 = 30 이 된다.

이 위치는 안에 폭탄으로 죽일 좀비가 둘이기 때문에 50 - 20 = 30 이 되는 것이다.

 

즉 폭탄이나 빈칸의 갯수를 투포인터로 계속 갱신해 나가고

그 폭탄이나 빈칸 갯수에 데미지를 곱한 값을 총 데미지에서 뺀 값이 그 위치에 줄 수 있는 기관총 데미지이다.

 

이제 각 위치의 좀비한테 기관총으로 줄 수 있는 데미지를 알아냈으니

각 위치의 좀비들을 순서대로 보면서 체력이 이 위치에 줄 수 있는 기관총의 데미지 보다 높은지 낮은지 보고

높다면 폭탄으로 처리 폭탄이 없다면 죽음을 출력하기만 하면 된다.

 

이렇게 하면 O(N)으로 해결이 가능하다.

3. 자바 코드

package Gold;

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

public class P19644좀비떼가기관총진지에도오다니 {

	// 현재 위치 앞 스코프에서 풀뎀 - Bomb의 갯수
	public static void main(String[] args) throws Exception {
		int L, Ml, Mk, C, map[], Bomb;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		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());
		boolean flag = true;
		map = new int[L];
		boolean Bomber[] = new boolean[L];
		int start = -Ml + 1;
		int end = 0;
		Bomb = Ml - 1;
		int shootDam = 0;
		int fullDam = Mk * Ml;
		while (true) {
			map[end] = Integer.parseInt(br.readLine());
			shootDam = fullDam - Bomb * Mk;
			if (shootDam < map[end]) {
				if (--C < 0) {
					flag = false;
					break;
				}
				Bomb++;
				Bomber[end] = true;
			}
			if (start < 0 || Bomber[start]) {
				Bomb--;
			}
			start++;
			if (++end == L)
				break;
		}

		System.out.println(flag ? "YES" : "NO");
	}
}

4. 마치며

설명을 조금 어렵게 한 것 같은데 이해하기 힘든부분은 댓글로 달아주시면 수정하도록 하겠습니당