[백준][Java] 10986번 나머지 합 (누적합, 수학)

 

문제가..

누적합인데 누적합 배열을 만들어서 풀면 안됨.. 오버플로우 나는듯..

그래서 런타임에러(ArrayIndexOutOfBounds)나는 것 같음 배열의 index가 음수여서는 안되니까

 

string배열로 하면 안되고 stringTokenizer로 해야되고

파훼법 기믹도 알아야 하고

long int실수도 안해야 한번에 해결 가능했었을듯

 

 

 

런타임 에러 (ArrayIndexOutOfBounds)

Java는 정수를 배열의 인덱스로 사용하며 JVM의 최대 정수 저장소는 2 ^ 32입니다. 따라서 배열에 2,147,483,647 개의 요소를 저장할 수 있습니다.

이거 런타임 에러 나는 이유가 애초에 preSum을 계속 누적시켜주면 안됨 무조건 Integet.MAX_VALUE 초과함계속 %M으로 나머지를 이용해서 문제를 해결해야함

누적합으로 푸는 것은 맞지만 누적합들의 나머지 값을 이용해야 오버플로우가 안납니다

 

 

 

틀렸습니다 왜why???

Line:28

int res = count[0];  (X)

long res = count[0]; (O)
int의 Max값은 2,147,483,647(2^31-1)입니다

틀렸습니다 왜why??

Line:29

(X)

        for(int i=0; i<M; i++) {

            res += (long)(count[i]*(count[i]-1)/2);

        }

 

(O)

        for(int i=0; i<M; i++) {

            res += (long)count[i]*(count[i]-1)/2;

        }

연산 부분에서 long처리 제대로 해줘야함..

(count[i]*(count[i]-1)/2) 이 부분에서

오버플로우 나는 듯 

 

 

 

 

 

기믹을 알아야 풀 수 있음

공부 출처 : https://girawhale.tistory.com/125?category=915305 

친절하게 알려주심

 

(S[j] - S[i-1]) % M = 0인 (i,j)의 쌍

S[j] % M = S[i-1] % M인 (i,j)의 쌍

 

※단, S[k] % M = 0인 경우의 k값. 즉 A1 + ... + Ak까지의 합이 M으로 나누어 떨어지는 경우는 쌍으로 안 묶어줘도 됨

이 말이 진짜 헷갈렸던게 뭔가 경우의 수를 생각 하려들면 더 헷갈림

S[k] % M = 0인 경우의 k값은 독자적으로 혼자서도 문제에서 요구하는 조건을 만족한다는건데

정확하게는 말로 풀어쓰려니까 너무 어려운데

여하튼 S[k] % M = 0 경우의 k값들은 따로 처리를 해줘야 한다는 말임

얘네들도 쌍으로 묶일 수 있는 조건을 만족하니까 근데 k값이 혼자 있는 경우에도 만족한다는 말임 다른 

S[x] % M = 1, 2, 3, .... , M-1 인 애들은 나누어 못 떨어지니까 쌍으로만 묶어줘야 문제에서 요구하는 조건을 만족함

 

이게 왜 헷갈리냐면 문제에서 요구하는 기본적인 조건

 [즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.]

가 숲이고 이걸 브루트포스로 풀어야 한다면 

 

(S[j] - S[i-1]) % M = 0인 (i,j)의 쌍

S[j] % M = S[i-1] % M인 (i,j)의 쌍

가 나무라고 생각하면

 

하여튼 결론은 이걸 처음 보고 풀 수 있는 사람이 존재하긴 하나 싶음

모듈러 연산이 괄호 분리되는 것도 몰랐고 (알긴 알았는데 까먹었음)

저걸 이항해서 (i,j)쌍을 구한다는 개념도 신박하고

쌍을 만들 필요 없는 가장 단순하게 0으로 나누어 떨어지는 구간은 따로 처리해줘야하는 점

 

틀렸습니다 단골 실수 int_Max 2,147,483,647 초과할 것 같으면 -> long으로 바꿔서 처리해줌

 

여기서 문제에서 자세하게 나와 있지 않았고, 수학이랑 너무 멀어져서 애매했던 점이

0이라는 숫자는 M으로 나누어 떨어지는가임

i=j인 경우가 존재하는가 뭐 이런 지금 돌이켜보면 말도 안되는 생각을 하니까

문제가 더 헷갈렸던 것 같음..

 

 

 

 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
 
public class Main {
        
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    
    public static void main(String[] args) throws IOException{
        String[] str = br.readLine().split(" ");
        int N = stoi(str[0]);
        int M = stoi(str[1]);
        
        int[] count = new int[M];
        int sum = 0;
        StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<N; i++) {
            sum = (sum + stoi(stk.nextToken())) % M;
            count[sum]++;
        }
        
       int res = count[0];
        for(int i=0; i<M; i++) {
            res += (long)count[i]*(count[i]-1)/2;
        }
        System.out.println(res);
        
        
        
//        bw.write("");
//        bw.flush(); 
//        bw.close();
    }
    
    private static int stoi(String input) {
        return Integer.parseInt(input);
    }
}