배열의 활용(구간합)

1차원 배열의 구간합

관련문제 : 백준11659번

파악

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 M회 구하는 프로그램을 작성하시오.

1 ≤ N ≤ 100,000
1 ≤ M ≤ 100,000
1 ≤ i ≤ j ≤ N

구상

값 입력 $\rightarrow$ 순회 $\rightarrow$ 합구하기의 $O(n)=N \times M = 10^{10}$ 이므로 시간 초과
구간합(누적합)을 구해 입력 순회후에 인덱싱으로만 구간합을 구하자

구현 : 값입력 $\rightarrow$ 누적합 $\rightarrow$ 출력(인덱싱)

원소 입력 loop에 누적합 구하기

for(int i = 1; i <= N; i++){ // Arr[0] = 0 으로 고정(누적합을 위해)
	int ele;
    cin >> ele; // 현재 입력되는 원소, Arr[i]번째의 원소(i=1부터 시작)
    sum = Arr[i-1] + ele; //구간합 구하기
}

출력

for (int i = 0; i < Query; i++){ // 질의 M회 출력
	int start, end; // start = i번째 수 , end = j번째 수
    cin >> start >> end;
	cout << Arr[end] - Arr[start-1] << "\n"; // 시작하는 지점 인덱스에서 -1 해야함
}

---

2차원 배열의 구간합

관련문제 : 백준 11660번

구현

입력

누적합 : 열 부분합 + 행 부분합 - 열.행 공통 합

for (int i = 1; i <= N; i++) // 행 순회
	for (int j = 1; j <= N; j++) // 열 순회
		int ele;
		cin >> ele;
		Arr[i][j] = Arr[i-1][j] + Arr[i][j-1] - Arr[i-1][j-1]

• 이를 위해선 배열 입력은 int i = 1부터 해야 함
• 위와 같이 입력받은 값을 누적하여 더하면, (1,1)에서 해당 좌표까지 드래그한 값과 같음

출력

예시 : (2,2) ~ (3,4) = {(1,1) ~ (3,4)} - {(1,1) ~ (2,1)} - {(1,1) ~(1,4)} + (1,1)
이를 위의 누적합 배열에서 표현하면,

int result = Arr[x2][y2] - Arr[x1-1][y2] - Arr[x2][y1-1] + Arr[x1-1][y1-1]

---

나머지 연산 + 구간합

관련문제 : 백준 10986번

파악

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ $10^6$, 2 ≤ M ≤ $10^3$)
둘째 줄에 N개의 수 $A_{1}, A_{2}, ..., A_{N}$이 주어진다. (0 ≤ $A_{i}$ ≤ $10^9$)
이 때에, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하라
(즉, $A_{i} + ... + A_{j} (i ≤ j)$ 의 합이 M으로 나누어 떨어지는 ($i, j$) 쌍의 개수를 구해야 한다)
1초 이내로, 메모리 제한은 256mb

문제에서의 배열의 갯수 $N = 10^6$ 이므로 완전 탐색 시에는 $O(n)=10^{15}$ 이므로 시간 초과
또한 배열의 크기가 $10^{15}$ 이므로, long 혹은 long long 자료형을 사용

구상

• "연속된 구간의 합" $\rightarrow$ "구간합(PrefixSum) 배열" 연상
• M으로 나누어 떨어진다 $\rightarrow$"나머지 연산의 분배 법칙" 연상
• "구간"이며, "M으로 나누어 떨어진다"는 것과 "나머지 연산의 분배 법칙"에서
  $\rightarrow$ 구간합 배열을 M으로 나누었을 때에, 나머지가 0인 경우,
  $\rightarrow$ 구간합 배열을 M으로 나누었을 때에 나머지 값이 동일한 두 구간(i,j)의 순서없는 조합(Combination)만큼의 구간이 존재.
  

구간합 배열에서 나머지 값이 동일한 두 구간(i, j) = M 으로 나누어 떨어지는 연속된 부분 구간의 합인 이유

구간 합 배열 $S$를 만들었을 때, 특정 구간 $i$부터 $j$까지의 합은 $S[j] - S[i-1]$로 표현됩니다. 이것이 $M$으로 나누어떨어지려면 수학적으로 다음 식이 성립해야 함

$(S[j] - S[i-1]) \pmod M = 0$

$S[j] \pmod M = S[i-1] \pmod M$

구간합 배열을 M으로 나누었을 때에 나머지 값이 동일한 구간을 구하기

• 나머지 값 M의 범위가 더 작으므로, Counting Array로 구하자

구현

배열(A)의 원소의 갯수를 N, 나누는 수를 M, 부분합 배열을 S, 배열 S의 원소 ele를 나눈 값을 remainder, 나머지값의 Counting Array를 C라 하자.
이 때에, 구간의 개수는 answer이다.

변수 선언

long answer; //
vector<long> S[N] = {0};
vector<long> C[N] = {0};

구간합 배열 S를 구하고

// 입력 로직
for (int i = 1; i <= N; i++){
	int ele; // 입력되는 값의 범위는 10^6 이하이기에 int로 지정
    S[i] = S[i-1] + ele;
}

S를 순회하며 M으로 나눈 나머지의 Counting Array를 구함

• remainder = 0인 경우를 answer에 더해줌

for (int i = 0; i < N; i++){
	int remainder = S[i] % M; // 
    if (remainder == 1){
    	answer++;
        }
    C[remainder]++;
    
}

Counting Array의 나머지 수가 동일한 경우의 경우의 수(Combination)을 구함

for (int remainder = 1; remainder <= M; remainder++){
// remainder가 0인 구간은 이미 "C"를 구할 때에 answer에 더해주었기 때문
	answer = answer + ((C[reaminder] * C[reaminder]-1) / 2); 
}

cout << answer << "\n";