문제 분석
N의 최대값이 106으로 작은편이지만, 이에 대한 모든 구간합을 구해야하므로 제한시간 1초안에는 해결하기 어려울 수 있다.
따라서 합 배열을 이용해야한다.
슈도코드
answer = 0;
N,M입력받기
N개의 수 입력받아 원본 배열 a에 넣기
합배열 sumArr 구하기
for(N만큼 반복) {
for(sumArr.size()만큼 반복) {
if(sumArr의 각 값이 M으로 나누어 떨어지면) answer++
}
int removeValue = sumArr의 첫번째 원소 삭제하며 리턴값 저장
for(sumArr.size()만큼 반복) {
sumArr의 각 원소의 값 = sumArr의 각 원소의 값 - removeValue
}
}
answer 출력Troubleshooting 1
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.io.IOException;
public class Main {
public static void main(String[] args) throws IOException {
ArrayList<Integer> a = new ArrayList<>();
ArrayList<Integer> sumArr = new ArrayList<>();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int answer = 0;
a.add(0);
sumArr.add(0);
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
for(int i = 1; i<N+1; i++) {
a.add(Integer.parseInt(st.nextToken()));
}
for(int i = 1; i< N+1; i++) {
int temp = sumArr.get(i-1) +a.get(i);
sumArr.add(temp);
}
for(int i = 1; i< N+1; i++) {
for(int j = 1; j < sumArr.size(); j++) {
if(sumArr.get(j) % M ==0) answer++;
}
int removeValue = sumArr.remove(1);
for(int j = 1 ; j < sumArr.size(); j++) {
int before = sumArr.get(j);
int after = before - removeValue;
sumArr.set(j, after);
}
}
System.out.println(answer);
}
}문제점
시간초과가 났다.
원인
수학적인 사고 없이, 그냥 진행해버리다보니 연산이 많아졌다.. 저 풀이는 결국 합배열을 계속 구하게되는거니까..!
해결
(A+B)%C = ((A%C) + (B%C))%C 를 이용!!
빼기 연산도 위와같은 규칙이 적용되므로, S[i] % M과 S[j] % M이 같으면, (S[i] - S[j]) % M = 0 을 생각하자.
즉 구간 합 배열의 원소를 M으러 나눈 나머지로 업데이트하고, S[i], S[j]가 같은 (i,j)쌍을 찾으면, 원본 배열에서 j+1부터 i까지의 구간 합이 M으로 나누어떨어진다는것을 알 수 있다.
Troubleshooting 2
import java.util.Scanner;
import java.io.IOException;
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[N]; //이 크기를 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<N; i++) { //여기를 N미만으로 했다가 런타임에러났다..!
if(C[i]>1) {
answer = answer + (C[i]*(C[i]-1)/2);
}
}
System.out.println(answer);
}
}문제점
백준에 제출하니 런타임에러가 났다.
원인
구글링 결과, 런타임에러에는 여러원인이 있다고한다.
여러 원인 중 하나가 인덱스 초과문제였다.
IDE에서는 잘 돌아가는데 왜 백준에서는 안돌아갈까? 아마 여러 테스트케이스 중 하나에서 인덱스 문제가 생기지않았을까싶다.
해결
C배열은 합배열의 각 값들의 나머지를 인덱스로 표시하기위한 배열이므로, C배열의 크기는 N이 아닌, M이 돼야한다.(0~(M-1))
따라서 마지막 for문도 M-1까지 루프 돌 수 있도록해야한다.
Troubleshooting 3
import java.util.Scanner;
import java.io.IOException;
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; //여기를 나머지 계산전에 S의 값만 int로 형변환했더니 런타임에러가 났다!
if(remainder == 0) answer++;
C[remainder]++;
}
for(int i =0 ;i<M; i++) {
if(C[i]>1) {
answer = answer + (C[i]*(C[i]-1)/2);
}
}
System.out.println(answer);
}
}문제점
long % int이기 때문에 계산결과는 long인데, 이를 int타입에 저장하려하니 타입 매치에러가 났다.
그래서 처음에 long타입만 int타입으로 바꿨는데 IDE에서는 잘 돌아갔는데 백준에서 런타임에러가 났다.
원인
배열S를 long타입으로 선언했고,따라서 값은 각각 long타입이라서 int범위를 초과하는 값을 가질 경우도있을것이다.
예제 입력에서는 int범위값만 주어졌기때문에 에러를 인식하지못했지만, 이 범위를 초과하는 값을 가지고있었는데, 이 값 자체를 int로 강제 형변환하려하면 에러난다!
해결
M의 범위는 확실히 int이고, M으로 나머지연산했을 때 결과의 최대값은 M-1이기때문에 결과도 역시 int범위내로 들어올것이다. 따라서 연산한 후 int로 형변환 해줘야한다!
int remainder = (int)S[i] % M; -> int remainder = (int)(S[i] % M);
제출 코드
import java.util.Scanner;
import java.io.IOException;
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++;
C[remainder]++;
}
for(int i =0 ;i<M; i++) {
if(C[i]>1) {
answer = answer + (C[i]*(C[i]-1)/2);
}
}
System.out.println(answer);
}
}공부한 내용
나머지 연산의 분배법칙
(A + B) % p = ((A % p) + (B % p)) % p
(A * B) % p = ((A % p) * (B % p)) % p
(A - B) % p = ((A % p) - (B % p) + p) % p순열과 조합
- 순열
서로 다른 n개중에 r개를 선택하는 경우의 수 (순서 상관 있음)
- 조합
서로 다른 n개중에 r개를 선택하는 경우의 수 (순서 상관 없음)
+서로 다른 n개중에 2개를 선택하는 경우의 수 (순서 상관 x) = n*(n-1)/2
주의할 점
-
인덱스의 값을 나머지로 갖는 값이 몇개인지 표현하는 나머지 배열을 만들어야한다!
-
인덱스의 값을 나머지로 갖는 값이 몇개인지 저장하는 배열의 크기는, 나누는 수이다!
ex) x%2가 가질 수 있는 값는 0 또는 1이므로 총 2개이다. -
nextInt()는 공백으로 숫자를 구분할 수 있다. 줄 바꿈으로 구분되는 숫자도 마찬가지이다.
공백으로 구분되다가 줄을 바꾸어서 넘어가는 경우도 nextInt()만으로 값을 가져올 수 있다. -
코테에서 자료형은 왠만하면 처음부터 long을 쓰자.
-
이 문제의 경우에는, 원본 배열이 필요하지않다. 이런경우에는 바로 합 배열을 만드는게 좋다.
-
나머지배열에서 나머지가 0인값은 배열의 처음부터 그 값까지로 인식해서, 나머지배열에서 0인 인덱스만 단독으로 정답으로 가져갈수도있다. 하지만 나머지가 0인 인덱스가 서로 다를경우, 이 두가지를 정답으로 가져갈 수도있기때문에 정답을 구할때에는 인덱스를 0부터 검사한다.
