[백준 골드 3] 10986번: 나머지 합

문제

https://www.acmicpc.net/problem/10986

10986번: 나머지 합

 

풀이

• N개의 수열이 주어졌을 때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구한다.
• Ai + ... + Aj 가 M으로 나누어 떨어지는 순서쌍 (i, j)를 구해야 한다.
• Si % M과 Sj % M의 값이 같다면 (Si - Sj) % M = 0이 되는 성질을 이용해야 한다.

누적 합을 가장한 모듈러 산술에 대한 문제이다.

여기서 모듈러 산술이란?

위키에 의하면 "정수의 합과 곱을 어떤 주어진 수의 나머지에 대하여 정의하는 방법" 이라고 한다.

무슨 소리인지 이해하기 어렵지만 나머지를 구했을 때 여러 연산이 가능하다는 특징을 이용한 것이라고 생각하면 된다.

 

대표적으로 정수 A, B, M에 대하여 A - B가 M으로 나누어 떨어질 때, A는 법 M에 대하여 B와 합동이라고 한다. 기호로는 A ≡ B (mod M) 이라고 쓸 수 있다.

( A - B ) % M 은 분배법칙이 성립하여 A % M = B % M 이 가능하다. 즉 누적 합을 M으로 나누었을 때, 나머지가 같은 것을 순서쌍으로 하는 (i, j)를 구하면 된다.

 

먼저, 입력된 N개의 수로 누적 합 배열을 만들어 준다. long 타입으로 정의하는 이유는 최대 10^9의 수가 10^6개 주어질 수 있기 때문이다.

long S[] = new long[N + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
    S[i] = S[i - 1] + Integer.parseInt(st.nextToken());
}

 

나머지에 해당하는 배열도 만들어 준다. M으로 나눈다면 나머지는 0부터 M - 1에 해당하는 값 중 하나가 될 수 있다. 이에 해당하는 remainArray를 정의한다.

누적 합 배열의 값은 처음부터 i까지 수의 합을 나타내므로 나머지가 0이 되는 경우, A1부터 Ai가 M으로 나누어 떨어지는 순서쌍 (1, i)를 만족하므로 Count 해준다.

long remainArray[] = new long[M];
long cnt = 0;
for (int i = 1; i <= N; i++) {
    int remain = (int) (S[i] % M);
    remainArray[remain]++;

    if (remain == 0)
        cnt++;
}

 

remainArray[i]에는 나머지가 i가 되는 경우의 수가 저장된다. 2 이상의 경우의 수가 된다면 두 수를 뽑아 순서쌍을 만들 수 있고, 순서에 상관 없이 두 개를 뽑는 경우이므로 조합 nC2가 된다.

nC2는 n * (n - 1) / 2 라는 식으로 표현 가능하다.

for (int remain = 0; remain < M; remain++) {
    if (remainArray[remain] > 1) {
        cnt += (remainArray[remain] * (remainArray[remain] - 1) / 2);
    }
}

 

전체 코드 (Java)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		long S[] = new long[N + 1];
		long remainArray[] = new long[M];
		long cnt = 0;

		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			S[i] = S[i - 1] + Integer.parseInt(st.nextToken());
		}

		for (int i = 1; i <= N; i++) {
			int remain = (int) (S[i] % M);
			remainArray[remain]++;

			if (remain == 0)
				cnt++;
		}

		for (int remain = 0; remain < M; remain++) {
			if (remainArray[remain] > 1) {
				cnt += (remainArray[remain] * (remainArray[remain] - 1) / 2);
			}
		}

		System.out.println(cnt);

	}

}

 

 

후기

누적 합과 나머지의 성질에 대해 이해가 필요한 문제였다. 조금 시간이 걸렸지만 스스로 해결할 수 있었다.