백준 10986번 자바 ☆

문제

https://www.acmicpc.net/problem/10986

10986번: 나머지 합

import java.util.Scanner;

public class Main10986_1 {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		long[] sum = new long[N];
		long[] dp = new long[M];
		long total = 0;
		
		sum[0] = sc.nextInt();
		for (int i=1; i<N; i++) {
			sum[i] = sum[i-1] + sc.nextInt();
		}
		
		for (int i=0; i<N; i++) {
			int temp = (int)(sum[i] % M);
			
			if (temp == 0) {
				total++;
			}
			dp[temp]++;
		}
		
		for (int i=0; i<M; i++) {
			total = total + (dp[i]*(dp[i]-1))/2;
		}
		
		System.out.println(total);
	}
}

1. (A + B) % C == ((A % C) + (B % C)) % C를 알고 있다면 문제 해결이 어렵지 않다.

마찬가지로 sum[i] % M == sum[j] % M 이라면 (sum[i] - sum[j]) % M은 0이다.

 

2. temp에 sum[i]의 나머지 값을 저장해주고 그 나머지값을 인덱스로 dp에 저장해준다.

위 문제를 예시로 들면

dp[0]	dp[1]	dp[2]
3	2	0

이와 같은 dp배열이 생성된다.

temp의 값이 0일 때, total 값을 증가시킨것과는 별개의 배열이다. sum[i] % M이 0이라는 것은 0번째 부터 i번째 구간의 합을 M으로 나눴을 때 나머지가 0이라는 뜻이기 때문이다.

 

dp에 저장된 값은 

2일 때 1

3일 때 3

4일 때 6

5일 때 10

으로 n * (n - 1) / 2로 점화식을 세울 수 있다. 즉 같은 나머지값( i ) 가지고, 개수가 n개 일때 두 개의 sum[i], sum[j]의 차이의 나머지가 0인 경우를 찾는 것과 같다.

 

3. sum, dp, total 변수들의 타입이 long인것에 주의하자. 이유는 입력값으로 주어지는 N의 범위를 최대으로 상정하면 쉽게 찾을 수 있다.

 

정리 : 나머지합에 대한 정리를 몰라서 풀지 못했다. 덕분에 오늘도 좋은 지식하나 배워간다.