[Baekjoon Online Judge] 19951. 태상이의 훈련소 생활 (Java)
핵심N과 M이 최대 100,000이다.완전 탐색 시, 최악의 경우 시간복잡도가 O(NM)이므로 시간초과이다. 이와 같이 큰 범위를 다룰 때, 시간을 줄이기 위한 방법의 하나로 누적합이 있다.누적합이름에서 유추할 수 있듯이 값을 계속해서 쌓는 것이다.e.g. [1, 2, 3, 4, 5] 의 누적합을 원소로 하는 배열은 [1, 3, 6, 10, 15] 기존 배열의 인덱스 2~4 범위의 합을 구하려면, 가장 단순한 방법은 해당 범위를 순회하며 일일이 합하는 것이다. 누적합 배열 acc를 이용하면 acc[4] - acc[1]로 O(1)에 계산할 수 있다. 이 문제의 경우는 누적합 아이디어를 사용하면 해결할 수 있다. 우선 상태를 기록할 새로운 배열 acc를 만든다.조교 1이 2~4번 칸에 흙을 3만큼 쌓으라고 ..
