Life Study

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

책에 나오는 구간합 문제의 끝판왕.. 역시나 문제 분석하기 파트에 나오는 식들이랑 말은 이해가 되지 않았고..
그렇게.. 삽질이 2~3일간 계속 지속됐다. 책에서는 실버 4의 난이도라고 되어있지만, 현재는 골드 3의 난이도다.
솔직히 필자는 실버문제들을 푸는데도 너무 오래 걸리고 이해하는 데에도 너무 어려웠는데 골드 난이도라니!
그래도 이왕 여기까지 온 거 이 문제를 대충 넘어갈 수 없었기에 이것도 분석을 해보았다.
문제 이름이 나머지 합 구하기라고 해서 진짜 나머지들을 구한 것들을 더하는 것이 아니라,
연속되는 숫자를 더한 값의 나머지가 0이 되는 순서쌍의 개수를 구해야 한다.
즉, 경우의 수의 개념 중의 하나인 조합이 들어간다는 것이다. 참고로 필자는 경우의 수나 조합 문제를 어떻게 풀었냐면,
경우의 수 같은 경우에는 일일이 노가다해서 풀었으며, 조합은 공식과 문제 형식을 단순암기해서 풀었다.
덕분에 시험지와 교과서는 노가다의 흔적으로 그 파트만 빽빽해지고 너덜너덜해졌던 기억이 난다.
하지만 걱정할 필요 없다! 지금이라도 조합에 대해서 제대로 알고 풀면 된다.
사실 필자도 이 문제 때문에 조합을 다시 공부했다.
조합이란, 서로 다른 n개의 원소를 가지는 어떤 집합에서 순서 상관없이 r개의 원소를 고르는 것이다.
위키백과에선 이렇게 설명하고 있어서 복잡해보일 수도 있지만, 예를 들어보자.
주머니에 10개의 구슬이 있다. 구슬들에는 번호도 없고. 색깔도 모두 같다. 그 중에 2개를 뽑는다고 가정하자.
그럼 그 구슬을 꺼내는데에 순서가 필요한가? 결과적으로 우리는 그 중에 2개의 구슬을 뽑은게 되는 것이다.
이렇게 뽑는 순서가 중요하지 않고, 결과적으로 먼저 뽑은 것을 제외한 나머지를 뽑게 된다면 조합을 사용하고,
순열은 뽑는 순서가 정해져있으며, 뽑은 것을 나열해야 한다면 사용하는 것이다.
순열의 기호는 \(_{n}P_{r}\)이고, 조합의 기호는 \(_{n}C_{r}\)이다. 이때, \(_{n}C_{r}\)은
$$\frac{n(n-1)(n-2)...\{n-(r-1)\}}{r!}$$

이때, 분자에 위치한 n은 r개 만큼 곱하는 것이다. 예를들어 10개 중에 2개를 뽑는다고 했을 때, 처음엔 10개중에 하나니까 10가지의 경우의 수가 있지만, 하나를 뽑고 나서는 9개의 경우의 수가 있기 때문에 10*9를 해준다. 여기서 2개만 하는 이유는 우리는 구슬을 2개만 뽑는 것이기 때문이다. 3개를 뽑는다면 8가지의 가능성이 또 생기기 때문에 10*9*8을 해줘야 한다. r!을 나누는 이유는 뽑은 순서는 다르지만 같은 구슬을 뽑았을 경우를 없애주기 위해서이다.
이제 문제를 풀기 위한 수학적 개념은 다뤘으니, 이제 다시 문제로 넘어와보자.
사실 필자는 문제 분석하기 파트의 나머지 합 문제 풀이의 핵심 아이디어 부분을 또 이해하지 못했기 때문에,
'이게 무슨 말이지' 하면서 분석했었다.
아래는 책에 적혀있는 핵심 아이디어 부분을 내 스타일대로 고쳐써본 것이다.

1. (A+B)%C = ((A%C) + (B%C))%C, 고로 (A+B)%C로만 계산해도 된다.
2. 합 배열 S[(현재항)] - S[(전 항)]은 원본 배열의 (전 항)+1 ~ (현재항)까지의 구간 합이다.
3. 구간 합 배열의 원소를 M으로 나눈 나머지로 업데이트하고 S[(현재항)]과 S[(전 항)]이 같다면 원본 배열에서
   (전 항)+1 ~ (현재항)까지의 구간 합이 M으로 나누어떨어진다는 것을 알 수 있다.
   (S[(현재항)]%M = S[(전 항)]%M 이면 (S[(현재항)] - S[(전 항)])%M = 0)

자, 이제 문제에 대한 분석은 끝났다. 코드로 넘어와보자.
합 배열 S에 누적합의 값을 저장해준다. 누적합의 자세한 설명은 https://life-study-1031.tistory.com/7

이 글에 자세히 있으니 누적합에 대해서 잘 모르겠다면 이 글을 참고해주면 된다.
누적합의 값을 저장하는 이유는 합이 M으로 나누어떨어지는 순서쌍을 구해야 하기 때문이다. 누적합을 구한 다음, M으로 나눠서 나누어떨어진다면 1항부터 그 항(n항이라고 가정하자)까지 더한 값이 나누어떨어지는 것이기 때문에 (1,n)이 성립되므로, 답이 될 수 있는 것이다.
그 다음으로는 조합의 개념을 이용하여 답을 구해야 되는데, 그러기 위해선 먼저 나머지의 개수를 셀 수 있어야 한다. 예를 들어보자. 나머지가 [1, 0, 0, 1, 0]일 경우, 0이 3개가 있다. 이때 0이 나오는 순서쌍은 각각 다를 것이다. 그렇게 0이 나오는 3가지 경우 중에서 i와 j에 해당하는 순서쌍을 순서와 상관없이 뽑는 것이기 때문에 \(_{3}C_{2}\)를 해야 하고, 그것을 위해서는 나머지의 개수가 필요하다. 물론 0하나에 i,j 순서쌍이 있기에 \(_{6}C_{2}\)가 아닌가요? 생각할 수도 있겠지만, 이렇게 되면 나머지가 0과 달라지는 순서쌍이 나올 수도 있기 때문에 \(_{3}C_{2}\)를 해야 한다.
여기서 질문이 나올 수 있다. 나머지가 0인 것들의 경우만 세면 되는데, 왜 굳이 0보다 큰 나머지들의 개수도 세는 것인가? 이는 문제를 분석할 때 3번에 해당하는 개념을 이용한건데, S[(현재항)]과 S[(전 항)]의 값이 같으면 (전 항)+1 ~ (현재항)까지의 구간 합이 M으로 나누어떨어지는 구간이기 때문에 0보다 큰 나머지의 개수도 세어주는 것이다.
구글링으로 찾은 풀이와 책에서 나온 풀이들의 공통점을 찾자면 S[i]%M의 값과 나머지를 저장하는 배열의 인덱스가 같다는 것인데, 이렇게 설정한 이유는 그 나머지의 개수를 구하기 위해서이다. 예를 들어, 나머지가 [1, 0, 0, 1, 0] 이렇게 나왔다면 사람은 0이 3개, 1이 2개 이렇게 셀 수 있지만 컴퓨터는 일일이 1씩 더해줘야 하기 때문에, 나머지를 저장하는 배열의 인덱스와 같게 한 것이다. 그림을 보면 이해가 쉬울 것이다.

이런 식으로 저장이 되는 것이다. 우린 이제 \(_{3}C_{2}+_{2}C_{2}\)의 값을 구하면 된다.

이제 풀이에 관련된 코드파트도 끝이 났다.

이번에는 수학의 개념과 코딩이 같이 나와서 필자도 이 글을 쓰는데에 3~4일 정도 걸린 것 같다.
내용이 정리가 잘 되지 않았기 때문이다. 이제는 작성하면서 많이 정리가 돼서 머릿속이 한결 깔끔해진 것 같다.
이번 내용을 요약하자면
① 이 문제를 풀기 위해선 수학적 개념 중 조합을 사용해야 한다.
    조합의 수식은 \(\frac{n(n-1)(n-2)...\{n-(r-1)\}}{r!}\)
② 나머지를 저장하는 배열의 인덱스 = 나머지 이렇게 연산을 해서 나머지의 개수를 세어준다.
    그 이유는 순서쌍의 경우의 수를 더해주기 위해서.
첫번째로 합배열 S에 나머지를 그대로 넣어서 계산하는 코드다.

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO 백준 10986번
		
        //입력을 빨리 받기 위해 BufferedReader 클래스를 이용해서 입력을 받음
        //BufferedReader 클래스로 입력을 받으면 문자열 파싱이 필요함.
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
        //N = 숫자를 입력받을 개수, M = 입력받을 숫자들을 나눌 숫자
        //sums = 합배열 S, count = 나머지 배열, answer = 순서쌍 개수
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		long[] sums = new long[N+1];
		long[] count = new long[1000];
		long answer = 0;
		
        //누적합 배열 만들기
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++) {
			sums[i] = sums[i-1] + Integer.parseInt(st.nextToken());
		}
		
		for(int i=1; i<=N; i++) {
			//sums[i]에 %M 연산을 하고 sums[i]에 다시 저장
            sums[i] %= M;
			
            //나머지가 0이면 answer를 더해줌 = 순서쌍의 개수를 세어줌
			if(sums[i] == 0) {
				++answer;
			}
			
            //나머지에 해당하는 인덱스에 1을 더해줌
			++count[(int)sums[i]];
		}
		
        //조합을 이용한 수식
        //2를 나눈 이유는 2! = 1*2 = 2 이기 때문이다.
		for(int i=0; i<count.length; i++) {
			if(count[i] > 1) {
				answer += count[i]*(count[i]-1)/2;
			}
		}
		
        //정답 출력
		System.out.println(answer);
	}

}

두번째로는 새로운 변수를 이용한 방법이다.

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

public class BOJ_10986 {

	public static void main(String[] args) throws IOException{
		// TODO 백준 10986
		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[] sums = new long[N+1];
		long[] count = new long[1000];
		long answer = 0;
		
        //이렇게 하면 for문을 1개만 써도 합배열 S의 값을 손상시키지 않고 계산하는 것이 가능하다.
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++) {
			sums[i] = sums[i-1] + Integer.parseInt(st.nextToken());
            //나머지를 저장하는 변수를 선언함.
			int rem = (int) (sums[i]%M);
			
            //나머지가 0이면 answer를 늘려준다.
			if(rem == 0) {
				++answer;
			}
			
            //나머지를 나머지 배열의 인덱스로 이용하여 나머지의 개수를 세어준다.
			++count[rem];
		}
		
		for(int i=0; i<count.length; i++) {
			if(count[i] > 1) {
				answer += count[i]*(count[i]-1)/2;
			}
		}
		
		System.out.println(answer);
	}
}