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

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

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

 

문제해결

• 시물레이션 같은 문제이지만 시물레이션으로 생각하고 구현하면 시간초과가 나기 쉽다.
• (O(n))으로 풀어야 한다.
• 기관총이 1부터 ml까지 영향을 주기 때문에 기관총에 영향을 받았을 때 체력이 남으면  수평 세열 지향성 지뢰를 쓰고 남지 않으면 기관총으로 끝내도록 한다.
• 수평 세열 지향성 지뢰를 쓰면 기관총과 달리 뒤에 2부터 ml까지 영향을 주지 못하기 때문에 cnt로 개수를 세고 영향을 받지 않는 경우도 생각을 한다.
• 이 때 1부터 ml까지 범위에만 영향을 주므로 투포인터나 que를 이용해서 계산을 하는 것이 좋을 것이다.
• 그래서 여기서는 큐를 이용해서 문제를 풀었다.

 

CODE

import sys
input = sys.stdin.readline
from collections import deque

l = int(input())
ml, mk = map(int,input().split())
c = int(input())
Z = [int(input()) for _ in range(l)]

que = deque()

cnt = 0
answer = True
for i in range(min(ml,l)):
    if cnt ==0:
        if Z[i]-mk*(i+1) <=0:
            que.append(0)
        else:
            que.append(Z[i]-mk*(i+1))
            cnt += 1
    else:
        if Z[i]-mk*(i+1-cnt) <=0:
            que.append(0)
        else:
            que.append(Z[i]-mk*(i+1-cnt))
            cnt += 1
for i in range(ml,l):
    if que[0] ==0:
        que.popleft()
        if Z[i]-mk*(ml-cnt) <=0:
            que.append(0)
        else:
            que.append(Z[i]-mk*(ml-cnt))
            cnt += 1
    else:
        que.popleft()
        if c>0:
            c -= 1
        else:
            answer = False
            break
        if Z[i] - mk*(ml-cnt) <=0:
            que.append(0)
            cnt -= 1
        else:
            que.append(Z[i]-mk*(ml-cnt))
if answer:
    while que:
        if que[0] ==0:
            que.popleft()
        else:
            que.popleft()
            cnt -= 1
            if c>0:
                c -= 1
            else:
                answer = False
                break
if answer:print('YES')
else:print('NO')