힌트만 원하신다면 힌트만 읽고 다시 풀고 오시고, 자세한 해설을 원하면 힌트 아래까지 읽으시면 됩니다:)

힌트: 2차원이 아닌 1차원이라고 생각해서 풀어보세요!

아래는 해설입니다.
.
.
.
.
.

언쟝
아래 현서님과 재준님이 이 문제의 풀이법 중 하나인 누적합에 대해 잘 설명해주셨습니다.
저는 누적 합까지 사고 하는 과정을 상세히 파헤쳐보려 합니다.

자 누적합에 대해 아무것도 모른다고 가정합시다. 우린 문제를 처음 마주했어요.

문제를 다 읽고 드는 생각은 아마 전부 계산하는 방법일겁니다. 그리고 제한 사항을 확인해보겠죠. N * M = 1,000,000이 나옵니다. skill 길이가 25만이므로 최악의 경우 25만 * 100만까지 계산하게 될겁니다. 시간복잡도는 O(NMlen(skill))이 됩니다. 해당 방법으로는 정확도는 어떻게든 맞추더라도 효율성에서 점수를 많이 깎아 먹을겁니다. 또한 문제가 요구하는 풀이도 아니겠죠. 자 그렇다면 계산 횟수를 어떻게 줄일까요?

바꿀 수 있고 바꿀 수 없는 것을 나눠봅시다. skill 길이는 최대 25만입니다. 바꿀 수 없죠. NM은 최대 100만이지만 모든 구간을 다 계산하지 않으면 이를 줄일 수도 있을겁니다. 따라서 NM은 우리가 바꿀 수 있는 요소입니다. 자 그럼 이를 어느 정도 까지 줄여야할까요? 파이썬 1초 == 2천만번 연산이라고 합시다. skill 길이는 최대 25만이므로 한 skill 연산당 최대 2천만/25만=8000번 계산할 수 있을겁니다. 쉽지 않군요. (NM)log2(NM)보다 낮아야합니다. log(N*M)=20 혹은 상수 시간만에 skill 한개에 대한 작업을 완료해야합니다. 어떻게 하면 skill 한개의 연산을 줄일 수 있을지 하나 하나 뜯어봅시다.

[5 5 5 5]
[5 5 5 5]
[5 5 5 5]

초기 값이 위와 같을 때 (0,1), (1,2)까지 2만큼 공격한다고 해보죠
[0 -2 -2 0]
[0 -2 -2 0]
[0 0 0 0]
위와 같은 공격을 할겁니다. 근데 당연히 위와 같은 공격을 하면 skill 연산 시간복잡도가 O(NM)이 되겠죠? 이를 어떻게 줄일까요? 저는 여기서 많이 헤멨습니다. 2차원을 전부 1차원으로 길게 펴봐도 어렵고. DP도 적용하기 쉽지 않고 이진탐색도 결국 O(NM)을 해결해야 해서 아무 의미가 없었습니다.

여기서 문제 해결의 포인트는 문제를 어렵게 만드는 요인이 2차원 배열인 것을 인지하고 1차원 배열로 생각해 볼 수 있어야합니다. 문제를 단순하게 만든 다음 다시 고차원의 문제를 해결하는거죠.

자! 1차원으로 생각해봅시다!

아래와 같은 배열이 있습니다.
[5 5 5 5]

[0 -2 -2 0]
(1) 연산을 해주려고 해요 어떻게 할까요? 여전히 O(N*M)이군요. -2가 반복되군요. 이를 한번에 계산할 수 없을까요?

[0 -2 0 0]
(2) 위와 같이 변환해준 후 -2를 누적해서 더하면 [0 -2 -2 0]과 비슷하게 만들 수 있겠네요. 근데 그럼 결과가 [0 -2 -2 -2]가 됩니다.

[0 -2 0 2]
(3) 자 이렇게 만들면 누적해서 더한 결과가 [0 -2 -2 0]이 됩니다.
네 누적합이죠. 1번 과정에서 누적합을 바로 떠올릴 수도 있습니다. 탑 다운 방식으로 어? 그건 누적합으로 해결할 수 있지! 하지만 이를 모르는 사람은 바탑업으로 해야하죠. 그게 1,2,3번이라고 생각합니다. 아무튼! 이제 1차원에서는 문제를 해결했으니 다시 2차원으로 키워갈까요?

[0 -2 -2 0]
[0 -2 -2 0]
[0 0 0 0]
(1) 자 이걸 어떻게 만들까요? 1차원에서 한 것과 최대한 비슷하게 만들어봅시다.

[0 -2 0 2]
[0 0 0 0]
[0 0 0 0]
(2) 이런 느낌이 되겠군요? 아까와 비슷하게 누적합 해봅시다.

[0 -2 -2 0]
[0 0 0 0]
[0 0 0 0]
(3) 원하는 결과와 비슷하게 나왔군요. 근데 이런 방식으로 계산하면 0행만 [0 -2 -2 0]이 되지 아래 행은 그게 안됩니다. 아래 쪽으로 전부 누적합 하면 되지 않냐구요? 해봅시다.

[0 -2 -2 0]
[0 -2 -2 0]
[0 -2 -2 0]
(4) 엇 비슷한 결과가 나왔군요. 마지막 행만 처리해주면 될듯해요. 3단계에서 어떻게 하면 마지막 행을 0 0 0 0을 할 수 있을까요? 1차원에서 어떻게 했었는지 떠올려봅시다.

[0 -2 -2 0]
[0 0 0 0]
[0 2 2 0]
(5) 네 맞습니다 위와 같이 하면 누적합이 우리가 원하는 위치만 -2가 될 수 있습니다. 그렇다면 위 행렬은 어떻게 만들까요?

[0 -2 0 2]
[0 0 0 0]
[0 2 0 -2]
(6) 정답에 가까워졌습니다. 위와 같이 만든 후 우측 방향으로 누적합하면 5번이 나오죠. 5번을 아래 방향으로 누적합하면 우리가 원하던 곳만 -2가 될겁니다.

자 이제 우린 어쩌다 보니 누적 합으로 문제를 해결하게 됐네요. 그럼 이제 누적 합의 특징을 파헤쳐 봅시다. 누적 합을 분석해놓아야 다음번에 누적 합으로 풀 수 있는 문제를 마주칠 때 누적 합을 떠올릴 수 있을겁니다.

누적합은 연속된 구간에서 특정 값을 더하거나 빼고 싶을 때 사용할 수 있습니다.
이때 연속된 구간을 1차원으로만 생각하면 안됩니다. 고차원에서도 연속된 구간은 성립합니다.

제가 생각한 방법이 비효율적일 수도 있고 좋게 추상화된 결론이 아닐 수도 있습니다.
더 나은 결론을 내리기 위한 과정으로 생각해주세면 감사하겠습니다.
피드백 언제나 환영합니다.