10986번 - 나머지 합

1️⃣ 부분 합, 모듈러 연산

 

✏️ 풀이 과정

N이 1000000까지 가능하기 때문에 O(N^2)의 알고리즘으로는 해결할 수 없습니다. 모든 결과를 구하는 것이 아니라 개수만을 구하면 되기 때문에 O(N)의 알고리즘으로 이를 해낼 수 있는지 알아봐야 합니다.

 

여기서 문제를 해결한 방법은 부분합을 사용한 것입니다. 부분합을 사용했을 때의 효과는 부분합 배열의 특정 인덱스에서 또 다른 인덱스의 값을 빼는 계산을 통해 특정 구간의 합을 알 수 있다는 것입니다.

 

여기서 M으로 나누어 떨어지는 구간을 골라야 하기 때문에 모든 계산에 M에 대한 모듈러 연산을 적용하면 더 간단하게 문제를 해결할 수 있습니다. 사칙연산에 대해 결합법칙이 성립하기 때문에 항상 적용해도 무방합니다.

 

문제 해결 아이디어는 부분합 계산 배열에서 모듈러 연산의 결과가 같은 인덱스끼리 묶어 하나의 구간을 찾아낼 수 있다는 것입니다. 주의할 점은 3개, 4개 등 2개를 초과하는 경우를 고려하지 않아야 한다는 것입니다. 그 이유는 예를 들어 1 1 1이 있다고 할 때 인덱스 0과 2를 잡으면 0, 1, 2 모두를 선택한 것과 같은 구간이 되기 때문에 중복계산이 됩니다.

 

부분합에 모듈러 연산을 적용한 결과가 0 0 1 0 1 이라고 할 때 가능한 구간의 조합은 0 세 개 중 두 개를 고른 것과 1 두 개 중 두 개를 고른 것의 합에 0 하나씩만 고른 것을 합한 3C2 + 2C2 + 3C1 = 7이 됩니다. 0 이외의 경우에는 한 개만을 선택했을 때 0이 되지 않기 때문에 한 개를 고른 경우를 고려하지 않습니다. 두 부분합 결과를 빼야 0이 나오기 때문입니다. (가열 초기 배열이 1 2 1이고 M이 3이라고 하면 부분합은 1 3 4 == 1 0 1이 됩니다. 인덱스 2까지의 부분합에서 인덱스 0까지의 부분합을 빼면 결과가 3이 되는데 이러한 원리로 0 이외의 경우에 부분합 0인 구간을 얻을 수 있습니다.)

 

즉 0의 경우 개수C1과 개수C2를 계산하고 나머지 숫자의 경우 개수C2를 하여 모두 더하면 결과가 나오게 됩니다.

 

⏱ 시간 복잡도

부분합 계산은 O(N)이며 컴비네이션 계산 또한 식을 이용하면 O(N)시간 내에 끝낼 수 있습니다. 따라서 전체 시간 복잡도는 O(N)이 되어 제한 시간 내에 해결할 수 있습니다.

 

💻 코드

JavaScript

const input = require("fs")
    .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt")
    .toString()
    .trim()
    .split("\n");

const [N, M] = input[0].split(" ").map(Number);
const remainder = input[1].split(" ").map((item) => Number(item) % M);
const partialSum = [remainder[0]];
const cnt = Array(N).fill(0);
cnt[partialSum[0]]++;
for (let i = 1; i < N; i++) {
    partialSum[i] = (partialSum[i - 1] + remainder[i]) % M;
    cnt[partialSum[i]]++;
}
let res = cnt[0];
for (let i = 0; i < N; i++) {
    res += (cnt[i] * (cnt[i] - 1)) / 2;
}

console.log(res);