[백준 10986] 나머지 합

😊 문제

백준 10986 - 나머지 합

😊 코드

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

public class Main {

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

		int n = Integer.parseInt(st.nextToken()); // 수의 개수
		int m = Integer.parseInt(st.nextToken()); // 나누는 수

		long count = 0;
		long sum[] = new long[n + 1];
		long remain[] = new long[m];

		st = new StringTokenizer(br.readLine());
		
		//누적합
		for (int i = 1; i < n + 1; i++) {
			sum[i] = (sum[i - 1] + Integer.parseInt(st.nextToken())) % m;			
			if (sum[i] == 0) {
				count++;
			}			
			//나머지가 같으면 +1
			remain[(int) sum[i]]++;
		}

		//나머지가 같은 n개 중에서 r개를 뽑는 모든 경우의 수
		for (int i = 0; i < m; i++) {
			if (remain[i] > 1) {
				count += (remain[i] * (remain[i] - 1) / 2);
			}
		}
		System.out.println(count);
	}

}

👌풀이

부분합 계산시 이중 for문을 사용하여 접근하였더니 시간 초과 발생

* 누적합

• S[i] 까지의 합 구하기

S[i] = S[i-1] + A[i]
S[i] = A[0]+A[1]+A[2]+ ... + A[i]

ex) S[4] = S[4-1] + A[4]
인덱스 4까지의 누적합 = 인덱스3(4-1) 까지의 합 + 인덱스 4
👉 6 + 1 = 7

* 구간합 - i부터 j까지의 합

• A[i]부터 A[j]까지의 합 구하기

S[j]-S[i-1]

* 경우의 수

• 나머지가 같은 인덱스 끼리 저장한 배열에서 (i, j) 조합 경우의 수 구하기
• n개의 수에서 r개를 뽑아 나열할 수 있는 경우의 수(중복 불가능)

nCr
n!/(n-r)!r!