[백준/자바] 10986 나머지 합 구하기

[백준/자바] 10986 나머지 합 구하기

 

📌 문제 

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

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

 

 

⚔ 입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)
둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109)

 

 

📣 출력

첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.

 

 

 

 

---

 

 

 

💎 문제분석하기

 

먼저 구간의 합 공식을 떠올려야 한다. 

 

누적 합 배열 

 

S[i] = S[i-1] +A[i] 

 

 

 

i ~ j 구간의 합

 

S[j] - S[i-1]

 

 

 

현재 문제에서는 구간의 합 (S[j] - S[i-1])을 M으로 나눴을 때 나머지가 0인 i,j를 찾아야 한다. 

따라서 

초기식 ( S[j] - S[i-1] ) & M = 0  

=> 모듈러의 정리에 따라서 분배 법칙이 적용되므로

=> ( S[j] % M ) - ( S[i-1] % M ) = 0

=> S[j] % M = S[i -1] % M 

 

 

따라서 결론적으로 구해야 하는 것은 나머지 값이 같아지는 상황을 만족시키는 S[j]와 S[i-1]

즉, 

i, j를 뽑는 경우의 수가 된다. 

 

한가지 주의할 점은, S[i] 자체가 0이 되는 상황을 포함시켜야 한다는 것이다. 

 

그래서 두가지로 나누어 계산을 수행하고 이를 더해주어야 한다. 

 

1) 합배열 자체가 %M =0이 되는 경우 

 

2) 합배열끼리 %M이 같아지는 경우 

 

 

---

1) 

 

예시로 입력되는 연속된 수의 배열은 1 2 3 1 2 이므로 이를 도식화하여 도출하면 다음과 같다. 

 

 

2) 

 

S[j] % M == S[i-1] %M 을 만족시키는 i, j의 순서쌍을 찾기 위해 먼저 

 

1. 같아지게 되는 상황을 구하고,

2. 그 중에 2개를 뽑는 계산을 진행하면 된다. 

 

M개로 나누는 상황에서 가능한 나머지는 M개이다. 

예를 들어 M=3인 경우, 나머지는 0, 1, 2개 발생. 

 

문제의 경우에 나머지는 0과 1로 발생한다. 

 

첫번째 연산 (같아지게 되는 상황 구하기)을 위해 배열을 생성한다. 

두번째 연산에서는 조합 공식을 사용한다. 

 

문제의 예로 들면 3과 2에 대한 조합 계산은 

 

3C2 + 2C2가 되므로 

 

 

 

카운트를 위해 만든 배열에는 자리마다 count +1 늘어주는 계산을 하여 구할 수 있으므로 

[ 3 2 ] 로 채워지게 될 것이다. 

 

이 배열에서부터 조합 계산은 다음과 같은 코드로 작성할 수 있다. 

 

 

 

 

더한 값을 answer 변수에 담아 출력한다. 

 

 

 

💡 코드 구현하기

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int M = sc.nextInt();

		long[] S = new long[N]; // 합배열
		long[] C = new long[M]; // 합배열%M을 동일하게 만들어주는 i,j를 담는 배열

		long answer = 0; // initiate answer

		S[0] = sc.nextInt();

		// 합배열 생성
		for (int i = 1; i < N; i++) {
			S[i] = S[i - 1] + sc.nextInt();
		}

		for (int i = 0; i < N; i++) {
			int remainder = (int) (S[i] % M);
			if (remainder == 0) {
				answer++;     // 구간합 자체가 0이 될 때 정답 카운팅  => 1번 계산 해결
			}
			C[remainder]++; // 나머지 개수 카운팅
		}

		for (int i = 0; i < M; i++) {
			if (C[i] > 1) {

				long cnt = C[i];                // 나머지가 같아지는 것을 만족시키는 합배열
				answer = answer + (cnt * (cnt - 1) / 2);    // 그 중 2개를 뽑는 조합 계산
			}
		}
		System.out.println(answer);

	}
}

 

 

 

 

 

 

 

 

 

---

 

 

 

풀이 참고 : Do it! 알고리즘 코딩테스트 - 자바 편