문제 풀이
이 문제는 2차원 배열에서 구간의 변화를 어떻게 효율적으로 처리할지가 관건인 문제입니다. 가장 쉽게 생각할 수 있는 브루트 포스로 풀 경우 정확성 테스트 케이스는 모두 맞출 수 있지만, 시간 복잡도가 O(N M K)가 되어 효율성 테스트케이스에서 시간 초과가 발생하게 됩니다.
2차원 배열에 대한 구간의 변화를 처리하는 방법을 설명드리기 전에, 우선 1차원 배열을 효율적으로 처리할 수 있는 방법을 설명드리겠습니다.
예를 들어, [1,2,4,8,9]의 배열이 있고, 0번째부터 3번째 원소까지 2만큼 빼야 하는 상황이라고 가정하겠습니다. 즉, 배열을 [-1,0,2,6,9]로 만들고 싶은 상황입니다. 가장 쉬운 방법으로는 0번째부터 3번째 원소까지 반복문을 사용해 2만큼 빼주는 방법이 있지만, 이 방법은 O(M)의 시간 복잡도가 걸립니다.
O(M)의 시간 복잡도를 O(1)로 만들 수 있는 방법은 바로 누적합을 이용하는 방법입니다. 위의 예시의 경우 [-2,0,0,0,2]를 저장한 새로운 배열을 생성합니다. 이 배열을 앞에서부터 누적합하면 [-2,-2,-2,-2,0]이 되기 때문에 초기 배열인 [1,2,4,8,9]과 더해주면 [-1,0,2,6,9]를 얻을 수 있게 됩니다. 즉, 1차원 배열의 a번째 원소부터 b번째 원소까지 c만큼의 변화를 주겠다고 하면 새로운 배열의 a번째 원소에 c를 더하고 b+1번째 원소에 c를 빼면 됩니다.
이 방식으로 문제를 풀면 O(N M K)의 복잡도를 O(N * K)로 줄일 수 있지만, 이 또한 시간 초과가 발생합니다.
따라서 이 아이디어를 2차원 배열로 확장해 줘야 합니다. 이번엔 2차원 배열에서 (0,0)부터 (2,2)까지 n만큼 변화시키는 경우를 예로 들어보겠습니다.
배열의 행만 따로 봐서 위에서 설명한 아이디어를 하나의 행씩 적용시키면, 1차원 배열의 0번째 원소부터 2번째 원소까지 n만큼의 변화를 3개의 행에 적용시키는 것이 됩니다.
n 0 0 -n
n 0 0 -n
n 0 0 -n
위 행렬을 다시 열만 따로 보면, 가장 왼쪽 열의 0번째 원소부터 2번째 원소까지 n만큼의 변화와 가장 오른쪽 열의 0번째 원소부터 2번째 원소까지 -n만큼의 변화와 같습니다. 각 열에 위의 아이디어를 적용시키면 아래와 같습니다. 이런 식으로 2차원 배열에도 적용시킬 수가 있습니다.
n 0 0 -n
0 0 0 0
0 0 0 0
-n 0 0 n
즉, 2차원 배열에서 (x1,y1)부터 (x2,y2)까지 n만큼의 변화는 (x1,y1)에 +n, (x1,y2+1)에 -n, (x2+1,y1)에 -n, (x2+1,y2+1)에 +n을 한 것과 같습니다. 위 배열을 위에서 아래로 누적합한 뒤, 왼쪽에서 오른쪽으로 누적합하거나 왼쪽에서 오른쪽으로 누적합 한 뒤, 위에서 아래로 누적합하면 처음에 의도한 (0,0)부터 (2,2)까지 n만큼 변화시키는 배열이 나오는 것을 확인할 수 있습니다.
n n n 0
n n n 0
n n n 0
0 0 0 0
이러한 방법으로 skill의 한 원소를 O(1)만에 처리할 수 있다는 것을 알 수 있습니다. 따라서 위의 방법으로 K개의 skill을 모두 처리할 수 있는 배열을 만드는데 O(K)가 걸리게 됩니다. 그리고 해당 배열을 누적합 배열로 바꾸는 과정이 필요한데, 행과 열을 각각 누적합 해줘야 하기 때문에 O(N M)가 걸리게 됩니다. 따라서 O(K + N M)으로 문제를 해결할 수 있습니다.
