[파이썬/python] 백준 - 19644 좀비 떼가 기관총 진지에도 오다니

문제

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

---

문제 설명

1. 킬로와 헥토에게 좀비가 1m씩 다가온다.
2. 좀비가 1m 다가올 때 마다 기관총 혹은 수평 세열 지향성 지뢰 중 1개를 선택하여 좀비를 공격할 수 있다.
   1. 기관총
      : Ml만큼의 사거리에 있는 모든 좀비에게 Mk 데미지만큼 공격할 수 있다.
   2. 수평 세열 지향성 지뢰
      : 1m에 있는 좀비를 즉사시킨다.
3. 좀비가 킬로와 헥토에게 도착하게 되면 둘은 죽게된다.
4. 좀비가 계속해서 다가올 때 최종적으로 킬로와 헥토가 살아남을 수 있는지 판단한다.

 

---

풀이

처음에는 단순하게 1m씩 다가오면서 완전 탐색을 진행해 보았지만, 시간초과가 발생했다.

최대 $L = 3*10^6, Ml = 3*10^6$이기 때문에 매 순간 L위치에서 Ml만큼 반복을 하게되면 약 $L*Ml =  10^{13}$정도로 문제의 시간 제한인 1초(약 $10^8$)를 초과하게 된다. 따라서 이를 해결할 수 있는 다른 방법이 필요했다.

 

두 번째로 각 위치에서 줄 수 있는 데미지를 누적해서 특정 위치에서 줄 수 있는 최대 데미지를 검사한다면 가능 할 것 이라고 생각했다. 하지만, 역시 그렇다고 하더라도 결국엔 L의 크기만큼 반복해야 하며 지뢰가 발생했을 때 Ml의 거리만큼에 데미지를 빼줘야 해서 이전과 마찬가지로 $L*Ml =  10^{13}$의 시간 소요가 되어 시간초과가 발생했다.

 

결국 L*Ml 중 Ml을 줄일 수 있는 방법이 필요했다.

지뢰를 사용하게 되면 현재 위치를 제외한 Ml-1미터를 이동하는 동안에는 Mk만큼의 데미지를 감소시켜야 했다.

그래서 지뢰를 사용할 때 마다 cnt를 Ml-1개 만큼 증가시켰다. 그리고 다음 좀비의 위치에서 데미지를 계산할 때 현재 cnt가 몇 개의 지뢰를 의미하는지 계산하여, 기존 Ml번 반복하여 중복되는 문제를 $O(1)$로 해결할 수 있도록 하였다.

이 문제에서는 지뢰를 어떻게 사용하는지가 핵심이었던 것 같다.

 

1. 각 위치에서 얼만큼의 데미지를 최대로 넣을 수 있는지 계산한다.
2. 현재 좀비를 죽일 수 있는지 확인한다.
   1. 좀비를 죽일 수 없다면 지뢰를 1개 사용하고 데미지 감소 cnt를 증가시킨다.
      1. 지뢰가 0개라면 "NO"를 출력하고 종료한다.
   2. 좀비를 죽일 수 있다면 cnt를 1 감소시킨다. (이 때 cnt가 0이라면 무시한다.)

---

코드

import sys
from math import ceil
input = sys.stdin.readline

L = int(input())
Ml, Mk = map(int,input().split())
C = int(input())
road = [int(input()) for _ in range(L)]

damage = [0 for _ in range(L)]

for i in range(Ml):
    if i > L-1:
        break
    damage[i] = Mk*(i+1)
for i in range(Ml,L):
    damage[i] = damage[i-1]


cnt = 0
val = Ml
if Ml > 1:
    val -= 1
for i in range(L):
    if damage[i] - Mk*(ceil(cnt/(val))) < road[i]:
        if C > 0:
            C -= 1
            cnt += Ml-1
        else:
            print("NO")
            exit()
    else:
        if cnt > 0:
            cnt -= 1
print("YES")

---

시간복잡도

• 총 L만큼 반복하기 때문에 최악의 경우 $L = 3*10^6$이므로 약 $O(3*10^6)$의  시간복잡도가 소요된다.