백준 19644번: 좀비 떼가 기관총 진지에도 오다니 문제풀이

문제 설명

• 기관총 사거리 ( M_L ): 기관총이 좀비에게 도달할 수 있는 거리
• 기관총 살상력 ( M_K ): 기관총이 좀비에게 주는 데미지
• 수류탄 개수 ( C ): 남은 수류탄 개수
• 진지 앞쪽 거리 ( L ): 좀비가 등장하는 총 거리
• 좀비 체력 ( Z_i ): 각 거리에서 좀비의 체력

좀비는 기관총 사거리 내에서 최대 ( M_K ) 데미지를 받습니다. 만약 이를 초과하는 체력이 남으면 수류탄을 사용해야 합니다. 수류탄이 없으면 게임은 실패(NO), 끝까지 방어할 수 있으면 성공(YES) 입니다.

---

문제 풀이 과정

1. 초기 입력 설정

import sys
input = sys.stdin.readline

L = int(input())  # 진지 앞쪽 거리
M_L, M_K = map(int, input().split())  # 사거리와 기관총 살상력
C_ammo = int(input())  # 수류탄 개수
answer = 'YES'

# 누적 데미지를 관리할 리스트
total_damage = [0] * (L + 1)

---

2. 좀비 방어 로직

주요 아이디어:

• 기관총 사거리 내 좀비에게 누적 데미지 계산
• ( \text{현재 데미지} = \text{총 데미지}[i-1] - \text{총 데미지}[i - M_L - 1] )
• 좀비 체력과 기관총 데미지 비교

for i in range(1, L + 1):
    zombie_HP = int(input())  # 현재 좀비 체력

    # 현재 좀비에게 가해지는 데미지 계산
    damage = total_damage[i - 1] - total_damage[max(0, i - M_L)]

    # 기관총 데미지로 좀비가 죽는 경우
    if zombie_HP <= damage + M_K:
        total_damage[i] = total_damage[i - 1] + M_K

    # 수류탄 사용이 필요한 경우
    elif C_ammo > 0:
        total_damage[i] = total_damage[i - 1]
        C_ammo -= 1
    else:
        answer = 'NO'
        break

print(answer)

---

소스코드 분석

핵심 로직 설명

1. 각 좀비 거리에 대해 누적 데미지를 관리
2. ( i ) 위치에서 누적 데미지는 기관총 사거리 내 데미지를 더하고, ( i - M_L )을 초과하는 데미지는 제외
3. 좀비 체력과 현재 기관총 데미지를 비교
4. 좀비가 살아있으면 수류탄을 사용하고, 수류탄이 없으면 종료

---

최적화 가능 부분

1. 메모리 사용 최적화:

   • total_damage 리스트 대신 변수 2개로 관리 가능

2. 조기 종료 조건:

   • 수류탄이 모두 소진된 상태에서 좀비 체력이 남으면 즉시 종료

---

결론

이 문제는 슬라이딩 윈도우 알고리즘을 통해 누적 데미지를 관리하는 방법이 핵심입니다. 주어진 조건을 충족하는 효율적인 방어 전략을 수립하기 위해 수류탄 관리와 기관총 데미지 계산을 잘 고려해야 합니다.

---