으아아 누적합 관련된 문제들을 풀고 가장 마지막에 풀어본 문제였는데 도저히 풀리지 않아 해답을 봤다.

해답을 봤는데도 이해가 안가 좀 더 공부하며 적어본다.

풀이를 보니 누적합을 이해하기 보다 모듈러 연산에 대해 알고 있는게 중요해보인다.

문제

백준 - 10986 나머지합

수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.

즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.

5 3
1 2 3 1 2

7 

길이가 N 인 수열에서 연속된 부분 구간의 합이 M 으로 나누어 떨어지는 구간의 개수를 구하는 문제이다.

해당 문제를 풀기 위해 내가 몰랐던 사전 지식들을 다시 되짚어본다.

해당 문제 풀이에 쓰인 사전 지식

1. 모듈러 산술

정보 보안 : 암호학 - 모듈로 연산(Modular Arithmetic)

모듈러 산술이란 어떤 수 A 가 M으로 나뉘어질 때 나머지가 B 인 경우 B = A mod M 으로 표현한다.

예를 들어 12 / 5 의 나머지는 2이기에 해당 값은 2 = 12 mod 5 라 표현한다.

다만 일반적인 나눗셈에서 나머지의 범위는 0이상의 수였으나 모듈러 산술에서 나머지는 음수,양수 모두 가능하며 다음과 같은 정의를 만족하는 연산을 모듈러 연산이라 한다.

• M으로 (B-A) 를 나눴을 때 나머지가 0이라면 (M|(B-4) 로 표현) B = A mod M 이다.

다시 위에서 들었던 예시인 12 mod 5 = ? 가 될 수 있는 값은 2뿐 아니라 7,12, ... , -3, -8이 모두 가능하다. (몫이 부족하거나 음수인 경우도 고려 가능하기 때문)

B = A mod M 일 때 M|(A-B) 를 만족하는 성질로 인해 다양한 성질들을 만족하는데 이번 알고리즘에 쓰인 성질은 모듈러 연산의 뺄셈 법칙이다.

모듈러 연산의 뺄셈 법칙 : (a-b) mod M = (a mod M - b mod M) mod M

이러한 특징은 더하기 , 곱셈 ,나눗셈 모두에게 동일하게 적용 된다.

위 연산이 가능한 이유를 두 가지 방식으로 설명 가능하다.

시계로 생각하는 모듈러 연산

첫 번째 방식은 시간이 M 까지 있는 시계가 있을 때 이 시계에서 A 만큼 우측으로 움직이고 B 만큼 좌측으로 움직이는 것은 A mod M 만큼 움직이고 B mod M 만큼 움직이는 것과 동일하다.

두 번째 방식은 연산으로 설명하도록 한다.

(a-b) mod M = (a mod M - b mod M) mod M 를 증명하기 위해 a mod M , b mod M 을 먼저 풀이하자. 각 값 a , b 는 다음과 같이 표기 가능하다.

• a = M * q1 + r1 (r1 = a mod M (나머지))
• b = M * q2 + r2 (r2 = b mod M (나머지))

a-b = M(q1 - q2) + (r1- r2) 로 표현 가능하며 양 변에 mod M 을 취해주면 다음과 같이 정리 된다.

• (a-b) mod M = 0 + (a mod M - b mod M) mod M

2. 누적합

누적합 알고리즘은 길이가 N 인 배열 A를 길이가 N인 누적합 배열 S 로 만들 때 다음과 같은 성질을 만족하는 배열을 누적합 배열이라 한다.

• S[i] = 1 <= i ? S[i-1] + A[i] : A[i]

이런 특징을 만족하는 누적합 배열 S는 다음과 같은 특징을 갖는다.

• 0부터 어떤 인덱스 i 까지의 합은 S[i]
• i < j 일 때 i 와 j 사이의 누적합은 S[j] - S[i]
• 1 <= i 일 때 S[i] - S[i-1] = A[i] , i 가 0일 땐 S[i] = A[i]

3. 중복 조합

중복조합은 N 개의 원소에서 중복을 허용하지 않고 r 개를 뽑을 때 (n! / {(n-r)! * r!}) 로 계산된다.

이러한 이유는 N 개의 원소에서 r 개를 뽑는 순열 (nPr) 로부터 계산된다.

n개의 원소에서 r 개 까지 뽑는 경우(비복원추출)의 수는 r개를 뽑을 때 까지 (n * n -1 * .... (n-r-1)) 이며 분모, 분자에 (n-r )! 를 곱해주게 되면 nPr = n! / (n-r)! 로 정리 할 수 있다.

이 때 비복원 추출로 뽑은 nPr에서 중복을 제거하기 위해 분모에 r! 를 곱해주면 nCr 은 위에서 말한 공식으로 계산 된다.

사전지식은 다 살펴봤고 문제를 풀어보자

백준 - 10986 나머지합

수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.

즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.

해당 문제는 배열 A 가 주어졌을 때 배열 A로 인해 생성한 누적합 배열 S를 이용해 구간의 합이 M 으로 나누어 떨어진느 구간의 개수를 구하는 문제이다.

연속된 부분 구간의 합이 M 으로 나뉘어 떨어진다는 것은 누적합 배열과 모듈러 연산을 통해 표현하면 이처럼 표현된다.

1. S[i] mod M = 0 (0부터 i 까지의 누적합 mod M 이 0)
2. i < j 일 때 (S[j] - S[i]) mod M = 0

그럼 다시 2번 조건을 풀이하면 다음과 같은 3번 조건을 구할 수 있다.

3.( S[j] mod M - S[i] mod M) mod M = 0 -> S[j] mod M = S[i] mod M

즉 , 누적합 배열에서 있는 구간들에서 mod M 의 값이 같은 값은 연속된 구간의 수를 구하는 것과 같다.

const fs = require("fs");
const path = require("path");
 
const filePath =
  process.platform === "linux"
    ? "/dev/stdin"
    : path.join(__dirname, "input.txt");
 
const inputs = fs.readFileSync(filePath).toString().trim().split("\n");
const [_, M] = inputs[0].split(" ").map(Number);
const A = inputs[1].split(" ").map(Number); // 일반 배열
 
const countArray = Array(M).fill(0);
let prefixSum = 0;
for (const value of A) {
  prefixSum += value;
  countArray[prefixSum % M] += 1;
}
 
let result = countArray[0];
 
for (let i = 0; i < M; i++) {
  const count = countArray[i];
  if (count > 1) {
    result += (count * (count - 1)) / 2;
  }
}
 
console.log(result);

배열 A의 i 번째 누적합의 나머지에 해당하는 개수를 세 countArray 에 담아준다.

• countArray[i] = 나머지가 i 인 값의 개수

예를 들어 배열 [ 1, 2, 3, 1, 2 ] 의 누적합은 [1,3,6,7,9] 이며 해당 누적합의 나머지 개수는 [3, 2, 0] 이다.

이제 개수를 세주면 된다.

1. 0부터 어느 구간 X 까지의 누적합 mod M 이 0이 되는 경우 = countArray[0]
2. 어느 구간 사이에 존재하는 나머지가 i인 구간의 좌표 (j) 들에서 시작점과 끝점 2개를 뽑는 경우의 수

[3,2,1] 의 countArray 에서 1번 조건을 만족하는 값은 3, 2번 조건을 만족하는 3C2 (3) + 2C2 (1) + 1C2 (0) 는 4로 결과는 7이 나온다.

회고

확실히 실버문제때와 다르게 좀 올라가니 여러 개념을 함께 섞어서 푸는구나 ..

조합쪽도 너무 약하고 모듈러 연산쪽 개념도 너무 약했다. 폐관수련 들어가자