[백준] 단계별로 풀어보기(단계:16, 누적합,JAVA)10986번, 나머지 합

문제 링크

10986번: 나머지 합

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

누적합이란?

입력되는 값들의 누적합 값을 따로 저장하여 필요에 따라 사용하는 알고리즘입니다.

 

예를 들어 1 5 4 36 8이 입력되었을 때 누적합 값을 저장한 배열을 표로 표현하면

	1	5	4	36	8
누적합	1	6	10	46	54

이 문제에 핵심은

1. 입력되는 수 N개에서 범위에 합이 M으로 나누어 떨어지는 개수를 구해야 합니다.

 

처음이 누적합을 이용하고 브루트 포스로 모든 경우의 범위를 계산하여 개수를 구하였지만 시간초과가 발생하였습니다.

 

브루트포스로 통과하지 못했기 때문에 다른 점화식이 존재할 것이라고 생각하였으며 여러가지 방법을 해보다가 발견하였습니다.

 

사용한 배열

 

DP[] : 누적합 저장 배열

 

점화식

 

누적합을 이용하여 연속하는 수 범위에 합을 구하는 방법(i : 시작 범위, j : 끝 범위)

해당 범위 합 = DP[j] - DP[i-1]

 

문제에서는 범위의 합이 M으로 나누어 떨어져야 하기 때문에 식을 이렇게 표현할 수 있습니다.

(DP[j] - DP[i-1]) % M = 0

모듈러 연산에 대한 법칙을 이용하면

DP[j] % M - DP[i-1] % M = 0

DP[j] % M = DP[i-1] % M

위와 같은 점화식을 얻을 수 있으며 위와 같은 범위가 존재하면 3으로 나누어 떨어진다는 것으로 확인할 수 있습니다.

점화식을 해석하면

1~j까지의 누적합 % M = 1~i-1까지의 누적합 % M이 같으면 i ~ j의 범위의 누적합은 M으로 나누어 떨어진다고 표현이 가능합니다.

 

만약

1~j까지의 누적합 % M = 2

1~i-1까지의 누적합 % M = 2이면

i~j까지의 범위는 M으로 나누어 떨어진다고 볼 수 있습니다.

 

예제입력 1에서 입력된 숫자에 대한 누적합을 표로 표현하면

	1	2	3	1	2
누적합	1	3	6	7	9

 

누적합에 대한 M(3)으로 나눈 나머지의 개수를 구하면

0	2(2번째)	3	2(5번째)
1	1(1 번째)	1(4 번째)
2

 

M으로 나누어 떨어지는 경우

1. 누적합이 M으로 나누어 떨어진다.

2. 위 점화식이 만족한다.

 

위 표를 보고 판단하면

1번에 만족하는 것은 M으로 나눈 나머지가 0인 개수 3개입니다.

 

2번에 점화식에 만족하려고 조합을 이용하였습니다.표에서 나머지가 0인 개수가 3개 중 같은 값이 2개가 나오는 경우를 구해야 합니다.

₃C₂ = 3! / 2!(3-2)! = 3개 = 2~3, 2~5, 3~5

나머지가 1인 개수가 2개 중 같은 값이 2개 나오는 경우는

₂C₂ = 2!/2!(2-2)! = 1개 = 1~4

 

3 + 1 = 4개위와 같은 방식으로 나올 수 있는 나머지의 값들의 조합의 합을 구하면 됩니다.

 

1번의 개수와 2번의 개수를 더하면 M으로 나누어 떨어지는 경우의 수를 구할 수 있습니다.3 + 4 = 7개

 

결과가 7이 출력됩니다.

 

조합을 구할 때 식은 아래와 같이 형태로 바꾸어 간단하게 구할 수 있습니다.

nC₂ = n! / 2!(n-2)! = n * (n-1) / 2 

 

문제를 해결한 알고리즘의 과정입니다.

1. 입력값 N과 M, N개의 수를 저장합니다.

2. N개의 값에 대한 누적합과 누적합을 M으로 나눈 나머지를 저장합니다.

3. 규칙1, 규칙2에 대한 개수를 더해서 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해 N개의 수를 분리하였습니다.
• N개의 수에 대한 누적합을 DP[]에 저장하였습니다.
• 누적합에 대한 나머지의 개수를 remains[]에 저장하였습니다.
• 규칙1과 규칙2를 적용하여 개수의 합을 result에 저장하였습니다.
• BufferedWriter에 result를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static long[] DP,remains;	//누적합 저장 배열, 나머지 개수 저장 배열
	static int N, M;
	public static void main(String[] arg) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        	//입력값 처리하는 BufferedReader
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        	//결과값 출력하는 BufferedWriter
        	//--------입력값 저장 및 배열 초기화-----------
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		DP = new long[N+1];
		remains = new long[M];
		st = new StringTokenizer(br.readLine()," ");
		for(int i=1;i<=N;i++) {
			int num = Integer.parseInt(st.nextToken());
			DP[i] = DP[i-1] + num;	//누적합 구하기
			long temp = DP[i] % M;	//나머지 구하기
			remains[(int)temp]++;		//나머지 개수 +1 하기
		}
		long result = remains[0];		//규칙1. 개수 결과에 더하기
        	//규칙2 개수 결과에 더하기
		for(int i=0;i<M;i++) {
			long temp = remains[i];
			result += temp * (temp-1) / 2;
		}
		bw.write(result + "\n");		//결과 BufferedWriter 저장
		bw.flush();		//결과 출력
		bw.close();
		br.close();
	}
}