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

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

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

int roadDistance, range, damage, mineCount;
int arr[3000001];
long long prevDamageSum[3000001];
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> roadDistance;
    cin >> range >> damage;
    cin >> mineCount;
 
    for (int i = 1; i <= roadDistance; i++)
    {
        cin >> arr[i];
 
        long long prevDamage = prevDamageSum[i - 1]; // 이전꺼 데미지 계승.
        long long offset = prevDamageSum[max(0, i - range)]; // 사거리만큼 이전의 요소
        long long curDamage = damage + prevDamage - offset; // 최종적으로 몬스터에게 가하는 데미지
 
        if (arr[i] <= curDamage) // 죽일 수 있으면
        {
            prevDamageSum[i] = prevDamageSum[i - 1] + damage; // 오프셋값은 반영하면 안된다.
            continue;
        }
        else // 죽일 수 없으면
        {
            if (mineCount >= 1)
            {
                --mineCount;
                prevDamageSum[i] = prevDamageSum[i - 1]; // 지뢰를 사용했기 때문에 이전 데미지 그대로 계승.
            }
            else
            {
                cout << "NO";
                return 0;
            }
        }
    }
        
    cout << "YES";
    return 0;
}

 

풀기위해 많은 우여곡절이 있었고, 덕분에 접해봐서 다행이라 생각한 문제이다.

아마 접하지않고 코딩테스트같은걸 봤더라면 절대로 못풀었을 문제이다.

사거리,데미지,폭탄의 개수를 주고 각 인덱스의 좀비를 죽일 수 있는지 없는지를 판단해야하는 문제이다.

 

각 값들이 매우 크기 때문에, O(N)으로 코드를 작성해야 한다. N이 최대 3백만이고 제한시간은 1초이기 때문이다.

이 문제에서 중요한 포인트는 지뢰이다. 지뢰가 터진다면 어떤 일이 발생하는가.. 를 잘 생각해야 한다.

문제에서의 조건에는 지뢰를 사용해야 할 경우, 기관총은 사용 못한다고 되어있다.

 

즉, 지뢰를 사용한다면 기관총의 유효사거리안에 있다고 하더라도 아무런 피해없이 한 칸 이동할 수 있게 된다.

바꿔말하면 지뢰가 터지면 이후에 특정구간만큼에 영향을 끼치게되는데(피해없이 이동),  여기서 그 특정구간이란 기관총의 유효사거리만큼을 의미한다.

 

예를들어 유효사거리 5인데 사거리 1인곳에서 지뢰를 터뜨렸다고 가정하자.

그러면 사거리 2,3,4,5의 좀비들은 아무런 피해없이 한칸씩 이동할 수 있다. 그 이후의 좀비들한테는 반영할 필요가 없다.

대충 아주 멀~리 있는 좀비들이 한칸씩 당겨졌다고 한들 의미가 없다고 생각하면 편하다.

 

순차적으로 입력값 들어왔을 때 이전에 지뢰가 터졌었다는 점까지 데미지를 계산해서 죽일 수 있는지 없는지를 판단해야하는데, 지뢰개수자체도 최대 3백만개라 각 입력마다 이전에 터졌던 지뢰를 일일이 확인하는 식으로는 해결할 수 없다.

 

이 모든걸 해결할 수 있는 방법이 '이전 데미지를 계승'하는 방식이다.

다만, 여기서 말하는 데미지는 이전에 줄 수 있었던 최종 데미지의 기대값이 아니다.

 

일단 유효사거리같은건 없다고 가정하고 각 인덱스에 비례해서 데미지를 줄 수 있다고 가정한다.

데미지가 3이라면

3 6 9 12 15 18 21 24 27 30 ......  

 

하지만 실제로 문제에서는 기관총의 유효사거리라는 조건이  실제하기 때문에, 이걸 반영해야 한다.

반영하는 방법으로는, 현재 인덱스에서 사거리만큼 이전 인덱스의 값을 빼는 것이다. (오프셋값)

 

prevDamageSum[i-1] // 이전 데미지값. 바로 위의 3 6 9 12 15 18....등의 값

prevDamage[i-range] // 오프셋값. 위의값에서 이 값을 뻄으로써 3, 6, 9, 9, 9, 9...라고 표현가능.

 

 실제 문제에서 원하는 형태의 숫자들이 나왔다. 

i - range가 음수값이 나오는 경우(사거리 이내의 i일 경우)는 0번째 인덱스값을 역참조하게 해놓는다.(0값)

-> prevDamageSum[max(0,i-range)]; // 음수값이면 0번째를 역참조

 

그러면 '계승할 이전데미지 값'은 아래와 처럼 된다.

prevDamageSum[i-1] - prevDamage[i-range];

여기서 기관총데미지를 더해주면 최종적으로 몬스터에게 가할 수 있는 피해량이 산출된다.

curDamage = prevDamageSum[i-1] - prevDmage[i-range] + damage;

 

이 값을 이용해서 몬스터를 죽일 수 있는지 없는지를 체크한 후, 죽일 수 없으면 지뢰를 사용한다.

죽일 수 있으면 마찬가지로 prevDamageSum[i]에 데미지를 계승하는데, 이때 오프셋값은 반영하지 않는다.

애초에 현재 로직이 반영하지 않는걸 기반으로 작성되었기 때문이다.

그러면 계승식은 아래와 같다.

prevDamageSum[i] = prevDamageSum[i-1] + damage; //  curDamage에서 오프셋값만 제외

 

죽일 수 없다면 지뢰개수를 한개 줄이고 마찬가지로 데미지를 계승해준다.

단, 지뢰를 사용했다면 해당턴에선 총을 쏘지 않았기 때문에 damage를 반영시키면 안된다.

그래서 계승식은 그냥 prevDamageSum[i] = prevDamageSum[i-1];이 된다.

 

테스트케이스를 찾아서 직접 코드한줄한줄 수행시키면서 확인하면 이해가 될거라 생각한다.

평소에 그래프쪽문제만 풀다가 그리디문제를 최근들어서 좀 풀고 있는데, 코딩테스트에서 내가 약한 모습 보였던 이유들을 확인 할 수 있는 시간들이였다.