[백준 10986] Java 나머지

 

[수도코드]

입력할 수 개수 n, 나눌 수 m 입력받기

n개의 수를 배열 a에 입력받기

구간 합 배열 s 저장 s[i] = s[i-1] + a[i]

for(n만큼 반복){

구간 합 중 m으로 나누어 떨어지는 (i, j) 쌍의 개수 구하기

}

결과값 출력

 

🟡시간 초과 코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        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());

        int s[] = new int[n+1];
        st = new StringTokenizer(br.readLine());
        for(int i = 1; i <=n;i++){
            s[i] = s[i-1] + Integer.parseInt(st.nextToken());
        }

        int cnt = 0; // (i,j) 쌍 개수 저장
        for(int i=1; i <=n; i++){
            for(int j = i; j <=n;j++){
                if((s[i] - s[j-1]) % m == 0){
                    cnt++;
                }
            }
        }
        System.out.println(cnt);
}
}

쌍 개수 구하는 부분에서 시간 초과가 발생했겠지.

 

🟢최종 코드

(s[i] - s[j-1]) % m = s[i] % m - s[j-1] % m == 0

> s[i] % m == s[j-1] % m

>> 합 배열을 m으로 나눈 나머지 값이 0인 개수 + 같은 원소의 개수의 경우의 수

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        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 s[] = new long[n+1];
        long c[] = new long[m];
        long cnt = 0; // (i,j) 쌍 개수 저장

        st = new StringTokenizer(br.readLine());
        for(int i = 1; i <=n;i++){
            s[i] = s[i-1] + Integer.parseInt(st.nextToken());
        }
        for(int i = 1; i <= n; i++){
            long remainder = s[i] % m;
            if(remainder == 0) cnt++;
            c[(int)remainder]++;
        }
        for(int i = 0; i < m; i++){
            if(c[i] > 1){
                cnt = cnt + (c[i] * (c[i]-1))/2;
            }
        }
        
        System.out.println(cnt);
    }
}

*값 커지니까 int말고 long으로 선언하기!

 

[Java / 백준 10986] 나머지 합