[10986] 나머지 합
문제 분석
배열이 주어진다.
특정 구간에서 (배열[i] + 배열[j]) % M == 0 이 성립하는 구간의 갯수를 구하여라.
특정 구간의 두 인덱스는 i <= j 의 조건으로 주어진다.
풀이 과정
🎯 수학을 잘 해야 한다..
예제 1을 보자.
5 3
1 2 3 1 2
5 는 주어질 수의 갯수다. (배열의 사이즈)
3 은 % M 의 M 이 된다.
두 번째 줄에는 순서대로 배열의 값이 주어진다.
int[] 배열 = {1, 2, 3, 1, 2};
// index = {0, 1, 2, 3, 4};index 0~1, 0~3, 1~4, 2~3, 3~4, 4~4 등등 특정 구간합의
모듈로 연산으로 0 ((배열[i] + 배열[j]) % M == 0) 이 된다면 정답 카운트가 되는데,
구해야 할 경우의 수가 많기 때문에 반복문을 통해 풀게 된다면 시간 초과가 난다.
for (int i = 0; i < size; i++) {
for (int j = i; j < size; j++) {
if((배열[i] + 배열[j]) % M == 0) result++;
}
}
// 위의 코드처럼 무지성으로 풀게 되면 시간초과가 난다.때문에 구간합을 이용하여 접근해야 한다.
해당 문제를 보고 구간합을 떠올려야 하며 왜 구간합으로 이용해야 하는지 수학적 사고가 필요하다.
🎯 왜 구간합이냐?
예제 1의 구간합을 구한다.
int[] 배열 = {1, 2, 3, 1, 2};
int[] 구간합 = {1, 3, 6, 7, 9}; // 구간합[i] = 구간합[i-1] + 배열[i];해당 구간합을 모두 모듈러 연산으로 업데이트 해주자.
예제 1의 피연산자는 3 이다. (모듈러연산[i] = 구간합[i] % 3)
int[] 배열 = {1, 2, 3, 1, 2};
int[] 구간합 = {1, 3, 6, 7, 9}; // 구간합[i] = 구간합[i-1] + 배열[i];
int[] 모듈러연산 = {1, 0, 0, 1, 0}; // 모듈러연산[i] = 구간합[i] % M;구간합을 쓰는 이유
- 모듈러연산의 모든 값들은 피연산자인
3을 넘지 못한다. (예제 1을 기준으로0,1,2중 하나다) - 여기서
0이 나온다는 것은 나누어 떨어졌다는 뜻이므로 정답을+1카운트 해준다. 구간합을 모듈러 연산으로 처리하고 나온 값들은 해당 값이 없으면0으로 나누어 떨어진다는 뜻이다.
🎯 3번 이유를 자세히 보자.
int[] 배열 = {1, 2, 3, 1, 2};
int[] 구간합 = {1, 3, 6, 7, 9}; // 구간합[i] = 구간합[i-1] + 배열[i];
int[] 모듈러연산 = {1, 0, 0, 1, 0}; // 모듈러연산[i] = 구간합[i] % M;모듈러연산[3] 은
배열[0],배열[1],배열[2],배열[3]의 값들을 모두 더한 것이다.- 이후
3으로 모듈러 연산을 한 것이다.
해당 값의 의미는 "만약 1 이 없다면 3 으로 나누어떨어진다" 는 뜻이다.
모듈러연산[1] 도 값이 1 인데 이 의미는 1 이 없다면 3 으로 나누어떨어지게 된다는 뜻이다.
1 이 없다는 뜻은 -1 을 해주면 되는 것이고,
같은 값을 가진 모듈러연산[i] 끼리 경우의 수를 찾으면 된다.
🎯 경우의 수 찾기
int[] 배열 = {1, 2, 3, 1, 2};
int[] 구간합 = {1, 3, 6, 7, 9}; // 구간합[i] = 구간합[i-1] + 배열[i];
int[] 모듈러연산 = {1, 0, 0, 1, 0}; // 모듈러연산[i] = 구간합[i] % M;모듈러연산[1] = 1, 모듈러연산[3] = 1 이다.
같은 값을 가진 모듈러연산[i] 가 2개 이상일 경우
2개의 경우의 수를 뽑는 공식을 적용할 수 있다.
if (count[i] > 1)
long result += (count[i] * (count[i] - 1) / 2);
// count[i] 의 값은 1이다. 모듈러 연산의 값으로 카운트해줘야한다.🎯 런타임 에러 (ArrayIndexOutOfBounds)
구간합을 구하기 위해 배열은 선언하니 런타임 에러가 뜬다..
그래서 배열없이 위의 로직을 수행하게 했다.
입력은 잘 받은 다음 구간합 배열을 long 변수 에 담자.
long[] count = new long[M];
long sum = 0;
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
sum += Integer.parseInt(st.nextToken());
int remainder = (int) (sum % M);
count[remainder]++;
}count 는 모듈러연산의 값들을 카운트해 줄 배열이다.
sum 은 구간합 배열 대신 사용할 변수다.
result = count[0];
for (int i = 0; i < M; i++) {
if (count[i] > 1) {
result += (count[i] * (count[i] - 1) / 2);
}
}정답을 0 의 갯수로 업데이트 해주고
반복문을 통해 2개 이상일 때, 2개 를 조합할 경우의 수 공식을 사용한다.
나의 생각
수학 유형이 나온다면 기존에 알고 있는 공식들을 이용해서 풀어야하는데 수학적 사고가 없어서 접근하기가 꽤 어려웠다.
블로그와 유튜브를 통해 원리를 찾아냈고 공식을 적용하니 쉬웠다.
수학 알고리즘은 꾸준히 오래 풀어야할 것 같다.
참고로 경우의 수 조합인 nCr 을 구현했지만 런타임 에러가 뜬다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
long[] count = new long[M];
long sum = 0;
long result = 0;
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
sum += Integer.parseInt(st.nextToken());
int remainder = (int) (sum % M);
count[remainder]++;
}
result = count[0];
for (int i = 0; i < M; i++) {
if (count[i] > 1) {
result += (count[i] * (count[i] - 1) / 2);
}
}
System.out.println(result);
}
// 런타임 에러..
private static long nCr(long number) {
long n = factorial(number);
long r = 2;
long nMinusR = factorial((number - r));
return n / (nMinusR * r);
}
private static long factorial(long number) {
if (number <= 1) return 1;
return factorial(number - 1) * number;
}
}
