파괴되지 않은 건물

누적합 알고리즘 (2022 카카오 - 파괴되지 않은 건물)

해당 문제는 정확성과 효율성을 모두 고려해야하는 문제이기 때문에 매 스킬마다 해당하는 구간을 계산하면 O(KNM)의 시간 복잡도가 나오게 되어 실패한다. 그래서 처음 생각했던 방법은 큐를 만들어 치유인 경우에는 큐에 더하고 파괴 스킬일 때 큐를 먼저 차례대로 실행 후 파괴하면 어떨까 했는데 효율성에서 1개 빼고 모두 시간초과가 떴다.. 혼자서는 방법을 못찾겠어서 찾은 방법이 누적합 알고리즘 누적합 알고리즘은 알고리즘 이름대로 나열된 수(구간)의 합을 구하는 알고리즘이다. 다만, 이전처럼 매번 모든 구간에 합을 적용하는 방식이 아니다. 문제는 2차원이지만 1차원에서부터 시작한다면.. 방식은 간단하다. 구간 [i..j] 까지 n을 더하면 arr[i] = n, arr[j+1] = -n 값을 넣는 방식으로 계산..