🐣 백준 11660 - 구간 합 구하기 5
1. 문제
- 수 N개 A1, A2, ..., AN이 주어짐
- 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수 구하기
- 즉, 구간 합 배열에서 M으로 나누어 졌을 때 나올 수 있는 구간들의 개수를 구하는 것
2. 입력
- 첫째 줄 N과 M
(1 <= N <= 10^6), (2 <= M <= 10^3) - 둘째 줄 N개의 수 A1, A2, ..., AN
(0 <= Ai <= 10^9)
3. 출력
- 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수 출력
4. 시간 복잡도
우선 문제에서 주어진 시간 제한은 1초이다
1억번정도의 계산정도까지만 가능한데 하나하나씩 구해서 하기엔 10^6 * 10^6 = 10^12 = 1조번해야 하기 때문에 패스
- 누적합 배열 계산, 각 누적합을 M으로 나눈 나머지 카운트 → O(N)
- 나머지 카운트를 이용해 조합 개수 세기 → O(M)
즉, 시간 복잡도: O(N + M) <= 10^6
5. 문제 분석
현재 문제에서 구해야 하는 건 구간의 합 (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)
여기서 우리가 구해야 하는 건 나머지가 같아지는 상황의 (i, j) 쌍 구하기
경우 1
(S[j] % M) == 0- 원본 배열 A의 (1 ~ j)까지의 합이 M의 배수
- 나머지가 0인 누적 합의 개수 카운트
경우 2
(S[j] % M) == (S[i - 1] % M)S[j]와S[i - 1]두 지점 사이 구간A[i]부터A[j]까지의 합이 M의 배수- 나머지가 같은 누적 합 그룹 안에서 2개를 뽑는 조합의 수를 구하기
예제 입력으로 비교 한다면
예제 입력 경우 1
(S[j] % 3) == 0S[2]=A[1]+A[2]S[3]=A[1]+A[2]+A[3]S[5]=A[1]+A[2]+A[3]+A[4]+A[5]
- 개수 3개
예제 입력 경우 2
(S[j] % 3) == (S[i - 1] % 3)- 나머지 0 그룹 -
S[0],S[2],S[3],S[5] - 나머지 1 그룹 -
S[1],S[4]- 나머지 0인 그룹에서 2개 뽑기 = 4 * 3 / 2 = 6
- 나머지 1인 그룹에서 2개 뽑기 = 2 * 1 / 2 = 1
💡 경우 1은 경우 2의 나머지 0인 그룹에 포함되는 개념이다
6. 코드 구현
package dataSource;
import java.io.*;
import java.util.StringTokenizer;
public class No_10986 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
//1. 수의 개수 N, 나누기 할 수 M 입력
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
long result = 0;
long[] S = new long[N + 1]; //누적 합 배열
long[] cnt = new long[M]; //나머지 카운트 배열
//2. N개의 수 입력 받으면서 구간 합 배열 저장
st = new StringTokenizer(br.readLine());
for(int i = 1; i <= N; i++) {
S[i] = S[i-1] + Integer.parseInt(st.nextToken());
}
//3. 구간 합 배열 S[i]를 M으로 나눈 나머지 저장 및 카운트
for(int i = 1; i <= N; i++) {
int remain = (int) (S[i] % M); // (int) S[i] % M에서 고치기
// 경우 1: 나머지가 0인 경우
if(remain == 0) {
result++;
}
// 현재 나머지에 해당하는 카운트 1 증가 (경우 2에 사용)
cnt[remain]++;
}
//4. 나머지 카운트 배열 cnt를 사용해서 경우 2 계산
for(int i = 0; i < M; i++) {
// 경우 2: 나머지가 같은 그룹 안에서 2개를 뽑은 조합 수
if(cnt[i] > 1) {
// nC2 조합: n * (n - 1) / 2
result = result + (cnt[i] * (cnt[i]-1)) / 2;
}
}
System.out.println(result);
}
}분명 이클립스에선 문제 없이 코드가 잘 실행됐다.. 그치만 백준에 제출을 하였는데
ArrayIndexOutOfBoundsException 런타임 오류가 발생했다
배열의 크기는 전혀 문제가 없어보인다 그러면 음수 인덱스를 사용한다는 것인데..
int remain = (int) S[i] % M;이 부분 때문에 발생하는 것 같다
S[i]는 long(누적합)인데, 연산자 우선순위를 보면 형변환 연산자가 산술 연산자보다 우선순위가 높기때문에 캐스팅을 먼저하고 %M을 하고 있다
즉, 누적합 배열은 int 범위를 넘어서 오버플로우가 발생했다
