이 문제는 합 배열과 부분 합을 이용해서 푸는 문제다.
이에 대해 자세히 모르면 구간 합 구하기4를 참고하자.
문제
설명
주의해야 할 부분
시간 제한 생각 없이, 구현만 하다 보면, 시간 초과로 틀리는 경우가 종종 있다.
시간 초과 코드 보기
이중 for문을 이용하니, 시간 복잡도가 O(n^2)이 되어 시간 초과가 되었다.
나머지 연산 분배법칙
시간 복잡도를 줄이기 위해 "모듈로 연산"을 적용해야 한다.
(A + B) % C = ((A % C) + (B % C)) % C
위 공식이 나머지 연산 분배법칙이다.
이에 대한 증명은 이 페이지를 참고하면 좋을 것 같다.
위 공식은 어디에 적용해야 하는 걸까?
일단 i~j의 구간 합은 S[j]-S[i-1]로 표현 가능하다.
그리고 문제 목표는 구간 합(S[j]-S[i-1])을 M으로 나눈 나머지가 0인 (i, j) 구간의 개수를 구하는 것이다.
즉, (S[j]-S[i-1]) % M = 0을 만족하는 구간의 개수를 구해야 하는 것이다.
이 식에 나머지 연산 분배법칙을 적용하면,
((S[j] % M) − (S[i−1] % M)) % M=0이 된다.
이 때, ((S[j] % M) − (S[i−1] % M))=0이면, 해당 i~j 구간합도 m으로 나누어 떨어진다고 할 수 있다.
물론 ((S[j] % M) − (S[i−1] % M))이 m의 배수여도 나머지 값은 0이 될 수도 있다.
예로 6 % 3은 0이 나온다.
그러나 이럴 경우는 없다.
왜냐하면,
만약 M = 3일 때, (S[j] % M)와 (S[i−1] % M)의 값은 0 ~ 2 사이가 된다.
따라서 ((S[j] % M) − (S[i−1] % M))의 최댓값은 2이므로,
3의 배수가 될 리는 없다.
결국, 구간 합(S[j]-S[i-1])을 M으로 나눈 나머지가 0일 때는,
((S[j] % M) − (S[i−1] % M))=0일 때,
즉, S[j] % M= S[i−1] % M일 때다.
모듈로 연산 적용
- 합배열 S를 생성하고, %M 처리를 해 준다.
- S[i] % M == 0 인 수 만큼, 정답 카운트를 올려준다.
- S[i] % M 값이 0이라는 뜻은, 원본 배열 A의 (1~i)의 구간 합이 이미 M으로 나누어 떨어진다는 뜻이기 때문이다.
- S[j] % M == S[i-1] % M 을 만족하는 (i,j)의 모든 경우의 수를 구한다.
- 즉, 나머지 값이 같은 인덱스 중 2개를 뽑는 모든 경우의 수를 구하면 된다.
- 왜냐하면, 문제에서 구하고자 하는 것(구간 합을 뜻하는 "S[j]-S[i-1]"을 M으로 나눈 나머지가 0인 경우)은
- S[j] % M= S[i−1] % M일 때이기 때문이다. 나머지 연산 분배법칙 참고
- 나머지 값이 같은 인덱스의 수를 저장하기 위한 배열 C를 생성한다
- C 배열을 이용해서, 나머지 값이 같은 인덱스 중 2개를 뽑는 모든 경우의 수를 구한다.
- 아래 예시에선, 0이 3개, 1이 2개이므로 3C2와 2C2의 합을 구하고 정답 카운트에 더한다.
- 즉, 나머지 값이 같은 인덱스 중 2개를 뽑는 모든 경우의 수를 구하면 된다.
그런데, 조합의 경우의 수는 어떻게 구할까?
경우의 수 - 조합
- nCr = nPr / r!이다.
- 이 때 우리는 나머지 값이 같은 인덱스 중 "2개를 뽑는" 경우의 수를 구한다.
- 즉, r = 2라는 뜻이다.
- 그럼, nC2 = nP2 / 2! = n X (n - 1) / 2!이다.
- 이 때, 위에서 C 배열로 나머지 값이 같은 인덱스를 저장했다. 따라서, C[i]가 n에 해당된다.
이젠 이를 전부 적용해서 코드를 짜보자.
정답 풀이
import java.io.IOException;
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws IOException {
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++; // 0~i까지의 구간합 자체가 0인 경우 정답에 더해주기
C[remainder]++; // 같은 나머지를 가진 인덱스의 개수 카운팅 해주기
}
for (int i = 0; i < M; i++) {
if (C[i] > 1) {
answer = answer + (C[i] * (C[i] - 1) / 2); // 같은 나머지를 가진 인덱스들중 2개를 뽑는 경우의 수를 더해주기
}
}
System.out.println(answer);
}
}내 정답 풀이
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
// n,m 입력받기
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());
// n개의 수 입력받기
int[] a=new int[n+1];
st=new StringTokenizer(br.readLine());
for(int i=1;i<=n;i++){
a[i]=Integer.parseInt(st.nextToken());
}
// 나머지 연산 적용한 합 배열 만들기
long[] s=new long[n+1];
for(int i=1;i<=n;i++){
s[i]=(s[i-1]+a[i])%m;
}
// 변형된 합 배열의 값이 0이면 cnt++
long cnt=0;
for(int i=1;i<=n;i++){
if(s[i]==0){
cnt++;
}
}
// S[j] % M == S[i-1] % M 을 만족하는 (i,j)의 수를 구한다
long[] newArr=new long[m];
for(int i=1;i<=n;i++){
newArr[(int)s[i]]++;
}
for(int i=0;i<m;i++){
cnt+=newArr[i]*(newArr[i]-1)/2;
}
System.out.print(cnt);
}
}시간 초과 코드
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
// n,m 입력받기
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());
// n개의 수 입력받기
int[] a=new int[n+1];
st=new StringTokenizer(br.readLine());
for(int i=1;i<=n;i++){
a[i]=Integer.parseInt(st.nextToken());
}
// 합 배열 만들기
int[] s=new int[n+1];
for(int i=1;i<=n;i++){
s[i]=s[i-1]+a[i];
}
// 이중 for문으로 m으로 나누어 떨어지는 구간 합 개수 구하기
long cnt=0;
for(int j=1;j<=n;j++){
for(int i=1;i<=j;i++){
long prefixSum=s[j]-s[i-1];
if(prefixSum%m==0){
cnt++;
}
}
}
System.out.print(cnt);
}
}주의점 메모
정답 코드 중 일부 배열을 선언할 때,
int형으로 하니 틀렸다. 나머지 코드는 완전히 동일해도 말이다.
그 부분만 long형으로 바꿔서 풀었더니 통과했다.
아마 오버플로우 때문이 아닐지 추측한다.
24.5.31) 다시 풀었지만 틀린 코드
import java.util.*;
import java.io.*;
public class Main
{
public static void main(String[] args) throws IOException{
// 수 N개 A1, A2, ..., A
// 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
// 출력
// 7
// 접근법
// 구간의 합이라니 합 배열 쓰일 거고
// 나누어 떨어진다라, 조합을 쓴 것 같은데
// 또 모듈러 연산 공식을 쓴 거 같아
// (a+b)%c=((a%c)+(b%c))%c
// 합 배열 공식은
// s[i]=s[i-1]+ a[i]인데,
// 딴 거 또 뭐가 있지
// 일단 예제 다루면서 떠올려 보자
// n=5, m=3
// 배열이 1,2,3,1,2 가 주어졌네
// 즉 어떤 연속된 부분의 합이 m으로 나누어 떨어지는 경우를 구해라고 하는데
// 투 포인터? 각각 가리키고 근데 포인터로 할 때 for 반복문 이중으로 안 될 것
// 합 배열은 1,3,6,7,9이고
// 기존 배열에서 %3을 하면1,2,0,1,2고
// 뭔가 %3에서 0이 되는 게 나누어 떨어지는 건데
// 구간 합 공식은 i~j까지의 합은 s[i]-s[j-1]
// 구간 합이 s[i]-s[j-1]인데, 여기에 모듈러 연산을 적용하는 거지
// 구간 합%3이 0일 때 카운트가 하나 증가하는데
// (s[i]-s[j-1])%3=0이라면, ((s[i]%3)-(s[j-1]%3)%3=0 이고,
// 즉 (s[i]%m)=(s[j-1]%m)이 될 때 모듈러가 0, 즉 나누어 떨어진다는 건데
// 그래서? 뭐 해야지? (s[i]%m)=(s[j-1]%m)이 될 때의 경우를 다 카운트하면 되잖아
// Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수
// 이중 포문으로 해야 하나? 그런데 n이 백만이고 이중이면 시간 초과라서 안 되고
// 1,2,3,1,2 원본 배열 a가 있고
// %m을 해서 1,2,0,1,2
// 여기서 a%m, b%m, c%m, d%m, e%m이 된 건데
// 이걸 합 배열 s로 만들면 1,3,3,4,6이 되고
// 또 이건 a%m, a%m+b%m, a%m+b%m+c%m ~~인데
// 다시 %m을 해서 1,0,0,1,0이 되고
// 이 때 1에서 시작하는 구간 합 중 0이 되는, 즉 나누어 떨어지는 게 3개라 cnt 늘려주고
// 나머지가 같은 값들, 즉 같은 원소일 때 (s[i]%m)=(s[j-1]%m)와 연관되지 않음?
// 즉 s에 %m을 각각 해서 만든 배열도 일종의 합 배열로 본다면
// 똑같이 구간 합 공식, s[i]-s[j-1]을 하는 식으로 모든 구간 합의 경우를 구할 수 있고
// (s[i]%m)=(s[j-1]%m)이 될 때 즉 같은 원소 값을 가진 거로 구성된 구간이 나누어 떨어진다는 말이 되고
// 이 때 조합을 사용해서
// 0인 것끼리 3c2의 경우를 구하고, 1인 것끼리 2c2의 경우를 구해서 더해서 cnt를 늘려주면
// 정답이 나옴
// 슈도코드
// n과 m을 받는다
// 수 n개도 받는다. 배열 a로. 인트형이지
// 합 배열 s를 만드는데
// a배열로 일단 기본 합 배열 1,3,6,7,9를 만들고
// 여기에 %m을 하면 1,0,0,1,0이 되네?
// a%m, (a+b)%m, (a+b+c)%m ~~인데
// a%m 단독으로 카운트 될 수 있는 이유는 Ai + ... + Aj (i ≤ j) 의 합
// 즉 i=j일 수 있기 때문
// 합 배열 만든 직후 0인 개수만큼 cnt 늘려주고
// 왜? 각 원소는 1부터 그 원소까지의 합이고, 그 구간 합이 %m을 했을 때
// 0이 되어 나누어 떨어지는 경우에 속하니까
// 조합 공식을 이용해서
// 원소 값이 같은 것을 카운트해서 따로 카운트 배열을 만들고
// 그 배열의 수만큼 조합을 적용하면 됨
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());
// 수 n개도 받는다. 배열 a로. 인트형이지
int[] a=new int[n+1];
st=new StringTokenizer(br.readLine());
for(int i=1;i<=n;i++){
a[i]=Integer.parseInt(st.nextToken());
}
// 합 배열 s를 만드는데
int[] s=new int[n+1];
long cnt=0;
for(int i=1;i<=n;i++){
s[i]=s[i-1]+a[i];
}
for(int i=1;i<=n;i++){
s[i]=s[i]%m;
// 합 배열 만든 직후 0인 개수만큼 cnt 늘려주고
if(s[i]==0){
cnt++;
}
}
// 디버그
// for(int i=1;i<=n;i++){
// System.out.println(s[i]);
// }
//조합 공식을 이용해서
//원소 값이 같은 것을 카운트해서 따로 카운트 배열을 만들고
//그 배열의 수만큼 조합을 적용하면 됨
// 뭐 할까? 그러닊 카운트 배열 어떻게?
// s배열이 잇고, 그 원소 중 같은 것끼리 ++하는 그런 배열
// s가 1,0,0,1,0이라면 s[1]은 1이고 그럼 1번 인덱스 ++,
// s[2]는0이고 그럼 0번 인덱스 값 ++ ~~
int[] count=new int[m]; //즉 %m해주면 무조건 나머지는 m보다 작잖아
for(int i=1;i<=n;i++){
int reminder=s[i];
count[reminder]++;
}
for(int i=0;i<m;i++){
// 계속 만든 배열 인덱스 돌면서
// 해당 값에 맞게 조합 공식을 적용하는 거지
// 조합 공식? npr/r!인데, 5p3은 5x4x3이지,
// 5c3은 5x4x3/3!이라서 10이 되고
// 어파이 ncr에서 r은 2로 고정이네
// 구간을 정의하는 i,j 두가지만 뽑을 거니까
// 그럼 nc2가 되고 그건 nx(n-1)/2가 되네
cnt+=count[i]*(count[i]-1)/2;
}
System.out.println(cnt);
}
}
// 첫 시도: ArrayIndexOutOfBounds가 떴는데
// 배열 다루는 곳에서 인덱스 넘어가는 곳 없는지 점검하기
// 보니까 int[] count=new int[m]에서
// 원래는 int[] count=new int[n]으로 선언했네
// 그러니 의도한 대로 작동 안 하고 반복문 다루다가 인덱스 에러 난 거지
// 이차 시도: ArrayIndexOutOfBounds?
// 또 왜? 분명 첫 시도에는 1%까지 진행된 후에 에러 떴는데
// 이번에 m으로 고친 뒤 하자마자 바로 에러 뜨니 내가 고친 것도 문제가 된 듯
// 일단 s 배열 원소 다 출력해 본 뒤 확인해야 겟어 => count[s[i]]++;부분 확인해보기
// 확인 했는데, 1,0,0,1,0으로 정상 출력됨을 확인함.
// 그럼 s[i]가 count의 범위를 벗어나서 에러가 뜬지 애매해짐
// 그럼 보니까 a,나 s 배열 다룰 때 인덱스는 다 정상으로 보임
// 결국 count 배열 선언하고 다룰 때 에러가 생긴 건데
이 코드는 런타임 에러 (ArrayIndexOutOfBounds)가 떠서 틀림
for(int i=1;i<=n;i++){
s[i]=s[i]%m;
if(s[i]==0){
cnt++;
}
}
=> s[i]=s[i]%m; 를 s[i]=(s[i-1]+a[i])%m;로 바꾸고 불필요한 for문 두 개를 하나로 합친 후 다시 했는데
이번에 10%까진 되다고 틀렸다고 나옴
???
=> 즉 추측하면 이 부분이 인덱스 에러와 직접적인 연관이 있던 걸로 보임. 단순히 s[i]=s[i]%m 했을 때 내 기대는 0~m-1까지의 원소만 있는 건데(%m의 나머지 값은 m보다 무조건 작으니까)
뭔가 더... 아닌가. 모르겠다
=> 이런 코드 붙잡긴 보단 다시 새로 처음부터 푸는 게 나을 듯하다.
물론 틀린 이유 찾는 게 중요함은 알지만
여기에 집착하면 말짱 도루묵이 됨을 고등학교 수학 시험 망치면서 깨달음
일단 지금 해결 안 되고 시간 많이 걸리는 건 패스하고 할 수 있는 것부터 해야 함을 깨달음
안 그럼 너무 시간 낭비하게 됨.
이런 건 수준 끌어올린 후 다시 풀 때 문제 생기면, 그 때가서 해결해
24.5.31) 인덱스 범위 오류 고쳐라고 지피티하고 얻은 코드(맞음)
//챗 지피티로 내 코드 수정해달라고 한 거임
import java.util.*;
import java.io.*;
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());
// 수 n개도 받는다. 배열 a로. 인트형이지
int[] a = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
a[i] = Integer.parseInt(st.nextToken());
}
// 합 배열 s를 만드는데
int[] s = new int[n];
long cnt = 0;
s[0] = a[0] % m;
if (s[0] == 0) cnt++;
for (int i = 1; i < n; i++) {
s[i] = (s[i - 1] + a[i]) % m;
if (s[i] == 0) {
cnt++;
}
}
int[] count = new int[m]; //즉 %m해주면 무조건 나머지는 m보다 작잖아
for (int i = 0; i < n; i++) {
int remainder = s[i];
count[remainder]++;
}
for (int i = 0; i < m; i++) {
cnt += (long)count[i] * (count[i] - 1) / 2;
}
System.out.println(cnt);
}
}
'CODING TEST > BOJ' 카테고리의 다른 글
| [Java]문제 007번 (백준 1940번) (0) | 2024.05.24 |
|---|---|
| [Java] 문제 006(백준 2018번) (0) | 2024.05.24 |
| [Java] 문제 004(백준 11660번) (0) | 2024.02.14 |
| [Java] 문제 003(백준 11659번) (0) | 2024.02.14 |
| [Java] 문제 002(백준 1546번) (0) | 2024.02.14 |
