Baekjoon 19644

01 Jul 2024 in Study / Computer science on Baekjoon 19644

Queue, Dynamic Programming

Baekjoon 19644

Description

킬로와 헥토는 좀비 떼로부터 탄약고를 사수하는 데에 성공했다. 포상 휴가나 조기 전역을 기대했으나 좀비 사태로 인해 계엄령이 선포되면서 오히려 전역이 연기되고 기관총 진지에 배치되었다.

전역이 연기된 킬로와 헥토에게 좀비 떼가 다가오기 시작했다.

기관총 진지 앞쪽 길의 거리는 L m이며, 진지로부터 i m 떨어진 곳에 있는 좀비의 체력은 Zi이다. 체력이 0 이하가 된 좀비는 영구적으로 죽는다.

기관총 진지에서 킬로와 헥토는 좀비가 1 m 이동할 때 기관총 또는 수평 세열 지향성 지뢰를 한 번 사용할 수 있다. 수평 세열 지향성 지뢰를 격발하는 경우 후폭풍을 피하기 위해 킬로와 헥토는 기관총 진지 밑으로 숨어야 한다. 즉, 수평 세열 지향성 지뢰 격발과 기관총 사격을 동시에 할 수는 없다.

기관총

유효 사거리는 진지 앞으로부터 ML m이다. 유효 사거리 내의 각 1 m 마다 좀비의 체력을 MK만큼 낮춘다.

기관총 탄약은 엄청나게 많이 있으므로 신경쓰지 않아도 된다. 총열 교체나 장전, 총기 이상 등을 고려할 필요 없이 계속 사격할 수 있다고 가정한다.

수평 세열 지향성 지뢰

유효 사거리는 진지 앞으로부터 1 m이다. 하지만 진지 바로 앞 1 m의 좀비는 체력과 상관없이 제압할 수 있다.

수평 세열 지향성 지뢰는 Cammo개 있다.

기관총 진지라곤 하나 콘크리트로 지어진 토치카가 아니라 사대로 구축한 임시 진지이기 때문에 1 m 떨어진 길 위의 좀비를 제압하지 못한다면 사망한다.

과연 킬로와 헥토는 살아남을 수 있을까?

Input

첫 번째 줄에는 기관총 진지 앞쪽 길의 거리를 나타내는 정수 L (1 ≤ L ≤ 3 × 106)이 주어진다.

두 번째 줄에는 기관총의 유효 사거리를 나타내는 정수 ML (1 ≤ ML ≤ 3 × 106)과 각 1 m 당 살상력을 나타내는 정수 MK (1 ≤ MK ≤ 100)가 빈칸을 사이에 두고 주어진다.

세 번째 줄에는 수평 세열 지향성 지뢰의 개수 Cammo (0 ≤ Cammo ≤ 3 × 106)가 주어진다.

네 번째 줄부터 L개의 줄에 걸쳐서 정수가 하나씩 주어진다. 이 때 i (1 ≤ i ≤ L)번째 정수는 기관총 진지에서 i m 떨어진 곳의 좀비의 체력 Zi (0 ≤ Zi ≤ 3 × 108)이다. Zi가 0인 경우 i m 떨어진 곳에 좀비가 없다는 뜻이다.

Output

킬로와 헥토가 살아남을 수 있다면 YES, 살아남을 수 없다면 NO를 출력한다.

Example I & O

Input
1
2 2
0
1

Output
YES

Input
1
2 2
0
3

Output
NO

Input
1
2 2
1
3

Output
YES

Input
6
3 2
1
2
4
6
6
6
8

Output
YES

Input
6
3 2
2
3
4
6
6
6
6

Output
NO

My solution

import java.util.Queue;
import java.util.LinkedList;
import java.io.*;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int L = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int Ml = Integer.parseInt(st.nextToken());
		int Mk = Integer.parseInt(st.nextToken());
		int Cammo = Integer.parseInt(br.readLine());
		Queue<Integer> q = new LinkedList<Integer>();

		int[] total_gun = new int[L + 1];
		total_gun[0] = 0;

		int[] new_gun = new int[L + 1];
		new_gun[0] = 0;


		for (int i = 0; i < L; i++) {
			int zombie_life = Integer.parseInt(br.readLine());
			q.add(zombie_life);
		}

		boolean flag = true;

		for (int i = 1; i < L + 1; i++) {
			int zombie = q.poll();
			new_gun[i] = 0;
			total_gun[i] = 0;

			if (i < Ml) {
				int previousGun = total_gun[i - 1];
				int update_zombie = zombie - Mk * previousGun;
				if (update_zombie <= Mk) {
					new_gun[i] += 1;
					total_gun[i] = previousGun + 1;
				}
				else {
					Cammo--;
					total_gun[i] = previousGun;
				}
			}
			else {
				int previousGun = total_gun[i - 1] - new_gun[i - Ml];
				int update_zombie = zombie - Mk * previousGun;
				if (update_zombie <= Mk) {
					new_gun[i] += 1;
					total_gun[i] = previousGun + 1;
				}
				else {
					Cammo--;
					total_gun[i] = previousGun;
				}
			}

			if (Cammo < 0) {
				flag = false;
				break;
			}

		}

		if (flag)
			bw.write("YES");
		else
			bw.write("NO");

		bw.flush();
		bw.close();
	}

}

Sketch
- Make Queue data structure having zombie life data
- Use dp algorithm like “Mortal Fibonacci Rabbits” posting in “Rosalind” Category
  - total_gun[i]: the number of gun firing toward i^th zombie
  - new_gun[i]: When i^th zombie is the head of queue, its value is 0 (Use Cammo) or 1 (getting fired)
  - When i^th zombie is the head of queue, the number of this zombie getting fired before arriving to the head (previousGun) = total_gun[i - 1] - new_gun[i - ML]
    - A shooting action when (i - Ml)^th zombie was head has no effect to i^th
- That is, the current life of head zombie is (original life) - Mk x (previousGun)
- Based on the current life of head zombie, we determine whether we use Cammo or just shoot
  - If we use Cammo, do Cammo–, total_gun[i] = previousGun, and new_gun[i] = 0
  - Otherwise, total_gun[i] = previousGun + 1 and new_gun[i] = 1
Code Analysis

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int L = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int Ml = Integer.parseInt(st.nextToken());
int Mk = Integer.parseInt(st.nextToken());
int Cammo = Integer.parseInt(br.readLine());
Queue<Integer> q = new LinkedList<Integer>();

int[] total_gun = new int[L + 1];
total_gun[0] = 0;

int[] new_gun = new int[L + 1];
new_gun[0] = 0;


for (int i = 0; i < L; i++) {
  int zombie_life = Integer.parseInt(br.readLine());
  q.add(zombie_life);
}

In java, BufferedReader and BufferedWriter are more efficient than Scanner and System.out

br(BufferedReader).readline() is used

For getting the data like “3 2”, we need to use StringTokenizer and Integer Wrapper Class

2 arrays for DP Algorithms

Queue with the data (lives of zombie)

boolean flag = true;

for (int i = 1; i < L + 1; i++) {
  int zombie = q.poll();
  new_gun[i] = 0;
  total_gun[i] = 0;

  ///

}

flag is connected to whether Cammo is zero or not
Loop with the number of queue’s data

Get i^th zombie

Initialization of new_gun[i] and total_gun[i]

for (int i = 1; i < L + 1; i++) {
  ///

  if (i < Ml) {
    int previousGun = total_gun[i - 1];
    int update_zombie = zombie - Mk * previousGun;
    if (update_zombie <= Mk) {
      new_gun[i] += 1;
      total_gun[i] = previousGun + 1;
    }
    else {
      Cammo--;
      total_gun[i] = previousGun;
    }
  }

  ///
}

When i < Ml, don’t need to consider “A shooting action when (i - Ml)^th zombie was head has no effect to i^th“
That is, previousGun = total_gun[i - 1]
current life of head zombie (update_zombie) = (original life) - Mk x previousGun
Left parts are for “Based on the current life of head zombie, we determine whether we use Cammo or just shoot”

for (int i = 1; i < L + 1; i++) {
  ///

  else {
    int previousGun = total_gun[i - 1] - new_gun[i - Ml];
    int update_zombie = zombie - Mk * previousGun;
    if (update_zombie <= Mk) {
      new_gun[i] += 1;
      total_gun[i] = previousGun + 1;
    }
    else {
      Cammo--;
      total_gun[i] = previousGun;
    }
  }

  ///
}

It is same with previous code block except “previousGun = total_gun[i - 1] - new_gun[i - Ml]”

for (int i = 1; i < L + 1; i++) {
  ///

  if (Cammo < 0) {
    flag = false;
    break;
  }
}

if (flag)
  bw.write("YES");
else
  bw.write("NO");

bw.flush();
bw.close();

Cammo < 0 -> They are dead

Baekjoon 19644

Description

Input

Output

Example I & O

My solution

Bioinformatics

Error

Description

Input

Output

Example I & O

My solution

Templates (for web app):

Error