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

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

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

 

진지 앞 쪽의 길이가 최대 300만이기 때문에 좀비를 한 칸씩 당겨가며 최적의 수를 고르는 것은 불가능하다(O(N^2)).

따라서 현재 좀비의 상태를 보고 기관총을 쓸 것인지, 지뢰를 쓸 것인지를 판단해야 한다.

 

만약 i 지점의 좀비를 사살할 때 이전의 어느 지점에서 지뢰를 쓰고, 어느 지점에서 기관총을 썼는지 알아야 한다.

그래서 다음과 같은 누적합 배열을 사용하였다.

s[i] = i지점 까지 기관총으로 준 대미지

이 배열로 현재 기관총으로 줄 수 있는 대미지를 구할 수 있다.

long long now = s[i - 1] - s[max(0, i - ml)] + mk;

s[max(0, i - ml)]을 뺀 이유는 ml 이후의 있는 적들은 기관총으로 죽일 수 없기 때문이다.

 

이렇게 하면 다음과 같은 두 가지의 경우를 나누어서 생각해 볼 수 있다.

1. now가 좀비의 체력보다 높은 경우: 지뢰를 사용해야만 사살할 수 있다. 만약 남아있는 지뢰가 없다면 "NO"를 출력해야 한다. 지뢰를 사용해서 사살할 경우 s[i] = s[i - 1] 이다.
2. now가 좀비의 체력보다 낮은 경우: 기관총으로만 사살할 수 있다. 이 경우 s[i] = s[i - 1] + mk 이다.

 

#include <iostream>
using namespace std;

long long a[3000001], s[3000001];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int l, ml, mk, c;
    cin >> l >> ml >> mk >> c;
    
    for (int i = 1; i <= l; i++) {
        long long now = s[i - 1] - s[max(0, i - ml)] + mk;
        cin >> a[i];
        if (a[i] <= now) {
            s[i] = s[i - 1] + mk;
            continue;
        } else {
            if (c) {
                c--;
                s[i] = s[i - 1];
            } else {
                cout << "NO";
                return 0;
            }
        }
    }
    cout << "YES";
}