[백준 11986] 나머지합 구하기 - JAVA

 

 

문제

N개의 수 A1, A2, ..., An이 주어졌을 떄 연속된 부분의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.즉, Ai + ... +Aj(i<=j)의 합이 M으로 나누어 떨어지는 (i,j)쌍의 개수를 구하시오.

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 10M(10⁶), 2 ≤ M ≤ 10k(10³)). 둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 10G(10⁹)

 

문제 분석

1. N의 최대값은 10^6, 모든 구간의 합을 구하면 자료형의 범위를 넘어설 수 있고, 0.5초 컷 하기엔 너무 오래걸린다.

2. (A+B)%C == ((A%C) + (B%C))%C 

3. 구간합 배열 공식을 이용해 (i+1, j) 구간합 구하기.  S[j] - S[i]

4. S[j] % M 과 S[i] % M의 값이 같다면 (S[j] - S[i]) % M은 0이다.

 이점으로 보아 구간합을 M으로 나눈 나머지로 업데이트 하고 S[j]와 S[i]가 같은 (i,j) 쌍을 찾으면,

 원본 배열에서 i+1 ~ j까지 구간합이 M으로 나누어 떨어지는 것을 알 수 있다.

5. 구간합 배열에서 0은 이미 구간 값이 0이므로 정답에 더해주고, 0의 경우의 수들과, 구간합들 중 M으로 나누어 떨어지는 것들의 경우의 수를 구하면 된다.

 

공식

배열 A = 1 2 3 1 2
합배열 S

 

1. N의 개수를 입력받으면서 합 배열 생성 합배열 공식

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

 

2. 구간 합 구하기

S[j] - S[i-1]

 

3. 경우의 수 계산하기

C[i] 개 중에서 2개를 고른다 = C[i]C2

nC2 = n * (n-1) / 2

 

---

pseudo code 작성하기

N(수열 개수), M(나눌 수) 저장하기
S(합배열), C(같은 나머지의 인덱스를 카운트하는 배열) 선언하기

for(N만큼 반복) {
    합 배열 생성하기 S[i] = S[i-1] + A[i]
}

for(i -> 0~N) {
    remainder = S[i] % M
    if(remainder == 0) {
        정답 += 1
    }
    C[remainder]의 값 1 증가
}

for(i -> 0~M) {
    C[i] (i가 나머지인 인덱스의 개수)에서 2가지를 뽑는 경우의 수 정답에 더하기 (C[i] * C[i]-1)/2
}

결과 출력

 

 

code

Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
long[] S = new long[N];
long[] C = new long[M];
long answer = 0;
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++;
    }
    C[remainder]++;
}

for (int i=0; i<M; i++){
    if (C[i] > 0) {
        answer = answer + (C[i] * (C[i] -1) / 2);
    }
}

 

---

결과 확인

입력	출력
5 3 1 2 3 1 2	7