[백준][JAVA] 10986번 나머지 합

10986번: 나머지 합

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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());
		
		long[] cnt = new long[m];
		long ans = 0;
		long s= 0;
		st = new StringTokenizer(br.readLine());
		for (int i=0; i<n; i++){
			s += Integer.parseInt(st.nextToken());
			long a = s%m;
			if (a==0) ans++;
			cnt[(int)a]++;
		}
		for (long i : cnt) {
			ans += i*(i-1)/2;
		}
		System.out.println(ans);
	}
}

 

설명

이중for문을 사용하여 모든 경우의 수를 확인했더니 시간 초과가 났다.

어떻게 풀지 모르겠어서 다른 사람들의 풀이를 찾아봤다. . 

먼저 누적합을 구해서 m으로 나눈 나머지 a를 구하고, 나머지값의 개수를 구하는 cnt 배열에서 cnt[a]의 값을 1 증가시킨다.

만약 a 값이 0이면 처음부터 해당 인덱스까지의 누적합이 m의 배수라는 뜻이기 때문에 ans를 1 증가시킨다.

 

cnt 배열을 이용해서 나머지값이 같은 인덱스 중 2개를 뽑는 경우의 수를 ans에 더해준다.