[Gold III] 나머지 합 - 10986
성능 요약
메모리: 160148 KB, 시간: 440 ms
분류
수학(math), 누적 합(prefix_sum)
문제 설명
수 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으로 나누어 떨어지는 구간의 개수를 출력한다.
누적합을 활용하면 되는 문제인데, 입력의 범위가 크기 때문에 단순히 누적합 배열로 모든 조합을 구하려고 하면 안 된다.
제시된 예제의 경우 나머지를 누적합한 배열을 만든다면 다음과 같이 될 것이다.
5 3
1 2 3 1 2
sum = {1, 3, 6, 7, 9};
res = {1, 0, 0, 1, 0};
이때 존재하는 부분 수열 중에서 나머지가 0인 수열의 개수를 찾는다면, 누적합을 구할 때처럼
res[end] - res[start-1] = 0 을 통해 찾을 수 있다.
이 조건은 res[end] = res[start-1]을 의미한다.
즉 가능한 조건은 res의 값들이 같은 index를 찾는 것이다.
입력이 최대 $$ 10^6 $$ 이기 때문에 res 값이 같은 두 수를 for문으로 찾으려면 시간이 많이 소요된다.
그래서 cnt 배열을 사용할 수 있다.
예를 들어 위 사례에서 나머지가 1인 index는 2개이다.
2개로 가능한 조합의 개수는 $$ _2C_2 $$로 1개가 된다.
즉, 가능한 나머지의 수를 count 배열로 만들어서 계산하면 된다.
주의할 점은 0의 경우 1로 시작해야 한다는 점이다. res[i-1]이 0이라면 0부터 i-1까지의 나머지는 res[i-1]이 되기 때문에 처음부터 시작하는 경우의 수를 포함해야 한다.
요약하자면 가능한 경우의 수는
$$ count[idx] * ( count[idx] - 1 ) $$
를 모두 더하면 되고, count[0]의 초기값만 1로 두면 된다.
package Gold.g3;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BOJ_1986_나머지합 {
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[] cnt = new long[M];
cnt[0] = 1;
st = new StringTokenizer(br.readLine());
long curr = 0;
for (int i = 0; i < N; i++) {
curr = (curr + Long.parseLong(st.nextToken())) % M;
cnt[(int) curr]++;
}
long ans = 0;
for (int i = 0; i < M; i++)
ans += cnt[i] * (cnt[i] - 1) / 2;
System.out.println(ans);
}
}
'Java' 카테고리의 다른 글
[백준] 2023 - 신기한 소수 (자바 Java) (0) | 2022.12.25 |
---|---|
[자바/Java] 예외 처리 (Exception) (0) | 2022.07.28 |
[자바/Java] 직렬화와 역직렬화, ObjectInputStream ObjectOutputStream, Serializable (0) | 2022.07.28 |
[자바/Java] 객체 참조 시 인터페이스 사용 이유 (0) | 2022.07.28 |
[자바/Java] 제네릭 Generics (0) | 2022.07.27 |