자바 백준 10986번 문제 : 나머지 합

문제 출처 : https://www.acmicpc.net/problem/10986

10986번: 나머지 합

 

문제 :

 

풀이 :

누적 합을 저장한 배열을 생성하고 이용한다.

s[i] % m == 0 인 경우, 인덱스 1부터 i까지의 누적 합이 m으로 나누어 떨어진다는 것이다.

인덱스 i부터 j까지의 구간 합은 s[j] - s[i-1] 이다.

구간 합이 m으로 떨어지는 경우를 구해야 한다.

( s[j] - s[i-1] ) % m = 0 해당 식을 정리하면

s[j] % m = s[i-1] % m 으로 정리할 수 있다.

i와 j가 같은 경우도 생각해야 하므로 i <= j 이다.

즉, s[j] % m == s[i-1] % m 가 성립할 경우, 구간 합이 m으로 떨어진다는 것이다.

 

j의 인덱스를 기준으로 구간 합이 m으로 나누어 떨어지는 구간의 개수를 각각 구해보자

 

소스코드 (오답 - 시간초과 & 오버플로우) :

import java.util.*;
class Main {
	public int solution(int n, int m, int[] arr) {
		int cnt = 0;
		// 누적 합 배열 생성
		int[] sArr = new int[n+1];
		for(int i=1; i<=n; i++) {
			sArr[i] = sArr[i-1] + arr[i];
		}
		// 누적 합을 m으로 나눈 s[i] % m 배열 생성
		int[] divArr = new int[n+1];
		for(int i=1; i<=n; i++) {
			divArr[i] = sArr[i] % m;
		}
		// 카운트
		if (divArr[1] == 0) cnt++;
		for(int j=2; j<=n; j++) {
			if (divArr[j] == 0) cnt++;
			for(int i=1; i<j; i++) {
				if (divArr[i] == divArr[j]) cnt++;
			}
		}
		return cnt;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] arr = new int[n+1];
		for(int i=1; i<=n; i++) arr[i] = sc.nextInt();
		System.out.println(T.solution(n, m, arr));
	}
}

 

아무래도 2중 for문 사용으로 인해 시간초과가 난 것 같다.

생각해보니 이렇게 2중 for문으로 매번 나머지가 동일한지 찾게 되면

O(N^2) 시간복잡도 이므로 시간초과 나는게 필연이라는 것을 깨달았다.

다시 태블릿을 켜서 어떻게 시간을 줄일 수 있는지 생각해보자

 

 

s[i]를 m으로 나눈 나머지를 인덱스로 하고, 그 나머지의 갯수를 저장한 cntArr 배열을 생성한다.

그 cntArr 배열을 이용해 카운트하면 2중 for문을 사용하지 않고 문제를 해결할 수 있다.

그리고 long형을 사용해 오버플로우 문제도 해결하였다.

*참고 nCr = nPr/r! = n!/(r!(n-r)!)

 

소스코드 (빠른 입출력 사용 X) :

import java.util.*;
class Main {
	public long solution(int n, int m, long[] arr) {
		long answer = 0;
		// 누적 합 배열 생성
		long[] sArr = new long[n+1];
		for(int i=1; i<=n; i++) {
			sArr[i] = sArr[i-1] + arr[i];
		}
		// s[i]를 m으로 나눈 나머지의 갯수를 저장한 cntArr 배열 생성
		long[] cntArr = new long[m];
		for(int i=1; i<=n; i++) {
			cntArr[(int)(sArr[i] % m)] += 1;
		}
		// 카운트
		answer += cntArr[0];
		for(int i=0; i<m; i++) {
			answer += (cntArr[i] * (cntArr[i] - 1) / 2);
		}
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		long[] arr = new long[n+1];
		for(int i=1; i<=n; i++) arr[i] = sc.nextInt();
		System.out.println(T.solution(n, m, arr));
	}
}

 

소스코드 (빠른 입출력 사용 O) :

import java.util.*;
import java.io.*;
class Main {
	public long solution(int n, int m, long[] arr) {
		long answer = 0;
		// 누적 합 배열 생성
		long[] sArr = new long[n+1];
		for(int i=1; i<=n; i++) {
			sArr[i] = sArr[i-1] + arr[i];
		}
		// s[i]를 m으로 나눈 나머지의 갯수를 저장한 cntArr 배열 생성
		long[] cntArr = new long[m];
		for(int i=1; i<=n; i++) {
			cntArr[(int)(sArr[i] % m)] += 1;
		}
		// 카운트
		answer += cntArr[0];
		for(int i=0; i<m; i++) {
			answer += (cntArr[i] * (cntArr[i] - 1) / 2);
		}
		return answer;
	}

	public static void main(String[] args) throws IOException {
		Main T = new Main();
		//Scanner sc = new Scanner(System.in);
		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[] arr = new long[n+1];
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=n; i++) arr[i] = Integer.parseInt(st.nextToken());
		System.out.println(T.solution(n, m, arr));
	}
}

 

이거 한번에 맞춘 사람이 과연 존재할까 ㄷㄷ..

앞으로는 시간복잡도와 오버플로우를 먼저 생각한 다음 문제를 풀어야겠다.