[알고리즘] Q005 나머지 합 구하기 (조합/Combination)

//N개의 수 A1,A2..An이 주어졌을때, 연속된 부분의합이 M으로 나누어 떨어지는 구간의 개수 구하기(제한시간: 1초)
//즉, Ai+...Aj(i<=j)의 합이 M으로 나누어떨어지는 (i,j)쌍의 개수 구하기

//입력값 
//1: N과 M (1<=N<=10^6, 2<=M<=10^3) 
//2: N개의 수 A1,A2..,An (0<= Ai<= 10^9) 

//분석하기 : 
//나머지 합 문제 풀이의 핵심 아이디어 :
//(A+B)%C 는 ((A%C)+(B%C))%C와 같다. 다시말해 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 이 구간 합의 나머지 연산을 한 값은 동일하다.
//구간 합 배열을 이용한 식 S[j] - S[i]는 원본배열의 i+1부터 j까지의 구간 합이다.
//S[j]%M의 값과 S[i]%M의 값이 같다면, (S[j]-S[i]) % M 은 0이다. 
//즉, 구간 합 배열의 원소를 M으로 나눈 나머지로 업데이트 하고 S[j]와 S[i]가 같은, (i,j)쌍을 찾으면 원본배열에서 i+1부터 j까지의 구간합이 M으로 나누어 떨어진다(=0)는 것을 알수있다.

/* 슈도코드 작성
 *  answer = 0 초기화
 *   
 *  N 입력받기
 *  M 입력받기
 *  S 선언하기(합배열. 길이 N+1)
 *  C 선언하기(같은 나머지 인덱스를 카운트 하는 배열) 
 *  
 *  for(i -> 0 ~ N){
 *  	N개의 수 입력받기 (A)
 *  	S[i] = S[i-1] + A[i] //합배열 저장 
 *  	remainder = S[i] % M //합배열을 M으로 나눈 나머지 값
 *  	
 *  	if(remainder == 0){
 *  		answer++
 *  	} 
 * 		C[remainder]++
 *  }
 *  
 *  for(i -> 0 ~ M){
 *  	C[i](i가 나머지인 인덱스의 개수)에서 2가지를 뽑는 경우의 수를 정답에 더하기 
 *  	//공식 : (C[i]*C[i]-1)/2
 *  }
 *  
 *  answer 출력
 * 
 * */
//결과
int answer = 0; 

//방법1 : use BufferedReader
//BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
//StringTokenizer st = new StringTokenizer(bf.readLine());
//st.nextToken();

//방법2 : use Scanner
Scanner sc = new Scanner(System.in);
int N 	= sc.nextInt();
int M 	= sc.nextInt();
long[] S = new long[N];
long[] C = new long[M];

for(int i=0; i<N; i++) {
    //step1. 합배열 저장
    if(i ==0) { 
        S[i] = sc.nextInt(); //합배열 첫번쨰값 저장
    } else {
        S[i] = S[i-1] + sc.nextInt(); //합배열 생성
    }

    //step2. 나머지 구하기
    int remainder = (int) (S[i] % M); 

    if(remainder ==0) { answer++; } //정답을 1증가				
    C[remainder]++; 				//나머지 인덱스 1증가				
}

for(int i=0; i<M; i++) {
    if(C[i] >1 ) {
        answer += (C[i]*(C[i]-1)/2);
    }
}
System.out.println("answer: "+ answer);

---

나머지 합 문제풀이의 핵심 아이디어: (A+B)%C 은 ((A%C)+(B%C))%C 와 같다.
 
다시말해, 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과
이 구간합의 나멈지 연산을 한 값은 동일하다. 

구간 합 배열을 이용한 식 S[j] - S[i]는 원본 배열의 i+1부터 j까지의 구간 합이다.
S[j] % M의 값과 S[i] % M의 값이 같다면, (S[j]-S[i]) % M은 0이다. 
즉, 구간합 배열의 원소를 M으로 나눈 나머지로 업데이트하고 S[j]와 S[i]가 같은 (i,j)쌍을 찾으면 
원본 배열에서 i+1 부터 j까지의 구간합이 M으로 나누어 떨어진다는 것을 알수있다.

---

728x90

여기서 잠깐...!

위의 수식에 대해 순간적으로 이해가 잘 가지 않는다.. 

우리의 친구 챗GPT에게 물어보자..!

알고리즘 중에 나머지 합 구하기를 공부하는 중인데 나머지 합 문제풀이의 핵심아이디어의 수식이 (A+B)%C 은 ((A%C)+(B%C))%C 와 같다고 하는데 이 부분이 수학적으로 이해가 잘 안되. 내가 수학적 개념이 좀 약해서.. 이 수식에 대해 자세하게 풀어서 설명해줄수 있어? 내가 생각했을떄, (A+B)%C 은 (A%C)+(B%C)와 같을꺼 같은데.. 왜냐하면 %C 부분이 (A+B)에 괄호를 풀고 %C를 각각 곱해준거와 같다고 생각했거든?

 

ChatGPT의 말:

ChatGPT

좋은 질문이야! 나머지 연산은 수학적으로 조금 헷갈릴 수 있지만, 차근차근 설명해볼게.

---

나머지 연산의 기본 개념

나머지 연산 %는 어떤 숫자를 특정 값으로 나눴을 때, 나머지를 구하는 연산이야.
예를 들어, A%CA \% CA%C는 AAA를 CCC로 나눈 나머지를 나타내.

• 예: 7%3=17 \% 3 = 17%3=1 (왜냐하면 7=3×2+17 = 3 \times 2 + 17=3×2+1, 여기서 나머지는 1)

---

수식의 의미

우리가 풀어야 할 문제는 다음 두 식이 같다는 것을 증명하는 거야:

(A+B)%C=((A%C)+(B%C))%C(A + B) \% C = ((A \% C) + (B \% C)) \% C(A+B)%C=((A%C)+(B%C))%C

이 식은 나머지 연산의 분배 법칙과 관련이 있어.

이게 왜 성립하는지 보자.

1. A%CA \% CA%C와 B%CB \% CB%C의 정의

• A%C=r1A \% C = r_1A%C=r1​ 라고 하면, A=k1×C+r1A = k_1 \times C + r_1A=k1​×C+r1​ (여기서 k1k_1k1​은 AAA를 CCC로 나눈 몫, r1r_1r1​은 나머지)
• B%C=r2B \% C = r_2B%C=r2​ 라고 하면, B=k2×C+r2B = k_2 \times C + r_2B=k2​×C+r2​

2. A+BA + BA+B를 CCC로 나눈 나머지를 구해보자

A+BA + BA+B를 써보면:

A+B=(k1×C+r1)+(k2×C+r2)A + B = (k_1 \times C + r_1) + (k_2 \times C + r_2)A+B=(k1​×C+r1​)+(k2​×C+r2​) A+B=(k1+k2)×C+(r1+r2)A + B = (k_1 + k_2) \times C + (r_1 + r_2)A+B=(k1​+k2​)×C+(r1​+r2​)

여기서 나머지는 r1+r2r_1 + r_2r1​+r2​ 부분에서 결정돼. 만약 r1+r2≥Cr_1 + r_2 \geq Cr1​+r2​≥C라면, 다시 CCC로 나눈 나머지를 구해야겠지.

즉,

(A+B)%C=(r1+r2)%C(A + B) \% C = (r_1 + r_2) \% C(A+B)%C=(r1​+r2​)%C

3. r1r_1r1​과 r2r_2r2​는 각각 A%CA \% CA%C와 B%CB \% CB%C였으니:

(A+B)%C=((A%C)+(B%C))%C(A + B) \% C = ((A \% C) + (B \% C)) \% C(A+B)%C=((A%C)+(B%C))%C

---

왜 (A+B)%C≠(A%C)+(B%C)(A+B)\%C \neq (A\%C)+(B\%C)(A+B)%C=(A%C)+(B%C)?

너는 (A+B)%C(A+B)\%C(A+B)%C가 (A(A%C) + (B%C)(A랑 같다고 생각했는데, 이는 항상 맞지 않아. 이유는 다음과 같아:

• (A(A%C) + (B%C)(A가 CCC보다 커질 수 있어.
  • 예: A=7,B=5,C=3A = 7, B = 5, C = 3A=7,B=5,C=3
    • A%C=1A \% C = 1A%C=1, B%C=2B \% C = 2B%C=2
    • (A%C)+(B%C)=1+2=3(A \% C) + (B \% C) = 1 + 2 = 3(A%C)+(B%C)=1+2=3
    • 하지만 3%C=03 \% C = 03%C=0, 그래서 결과는 달라질 수 있어.

---

요약

(A+B)%C=((A%C)+(B%C))%C(A + B) \% C = ((A \% C) + (B \% C)) \% C(A+B)%C=((A%C)+(B%C))%C가 성립하는 이유는 나머지 연산이 덧셈에 대해 분배 가능하기 때문이야. 하지만 (A+B)%C≠(A%C)+(B%C)(A + B) \% C \neq (A \% C) + (B \% C)(A+B)%C=(A%C)+(B%C)가 되는 경우는, (A%C)+(B%C)(A \% C) + (B \% C)(A%C)+(B%C)가 CCC 이상일 때 발생해. 그래서 추가로 %C\% C%C를 해줘야 정확한 결과를 얻을 수 있어.

---

 

나머지합 구하기 (=경우의 수)

순열과 조합에 대해 기본지식이 있어야 풀수있는 문제 

 순열 ( nPr ) 

순열이란 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미합니다. (순서 상관 있음)

 

 조합 ( nCr ) 

조합이란 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미합니다. (순서 상관 없음)

코딩으로 조합 공식 : 

• C배열 (같은 나머지 인덱스를 카운트 하는 배열) ==> 나머지값을 인덱스 i로 잡고 값으로 동일 인덱스의 갯수를 저장 
• 나머지가 같은 인덱스 중 2개를 뽑는 경우의수    ==> (C[i] * (C[i]-1)) /2
• 2개를 뽑는 경우를 구하는문제가서 C[i]-1/2가 되는거임..

---

순열을 구하는 공식에 대해 이해가 잘 가지 않는다.. 

이럴땐 우리의 친구 챗GPT에게 물어봐야지! 

# 나의 질문 : 

알고리즘을 공부하고 있는데 나머지 합 구하는 문제를 풀고있어 여기서 경우의 수에 대한 내용이 나오는데 예를들어 3개의 원소중 두개를 뽑는 경우의 수가 3C2 = 3 이라는 부분이 있거든? (순열에 대한 내용인거 같은데) 이 수식을 코딩적으로 풀어서 설명하면 (C[i] * (C[i]-1) / 2) 이렇게 된데. 순열을 잘 몰라서 더 이해가 안가는거 같은데 3C2 = 3 이라는 부분부터, 이게 어떻게 해서 (C[i] * (C[i]-1) / 2) 가 되는지 자세히 설명해줄수 있어?

 

(챗GPT 답변) :

좋은 질문이에요! 여기서 3C2 = 3이라는 표현은 **조합(combination)**을 나타냅니다. 이는 순서와 상관없이 주어진 집합에서 일부 원소를 선택하는 방법의 수를 의미합니다.

1. 조합의 기본 공식:

조합을 구하는 일반적인 공식은 다음과 같습니다:

nCk=n!k!(n−k)!nCk = \frac{n!}{k!(n-k)!}nCk=k!(n−k)!n!​

여기서:

• nnn: 전체 원소의 개수
• kkk: 선택할 원소의 개수
• !!!: 팩토리얼, 예를 들어 n!=n×(n−1)×(n−2)×⋯×1n! = n \times (n-1) \times (n-2) \times \cdots \times 1n!=n×(n−1)×(n−2)×⋯×1

예를 들어, 3C23C23C2를 계산해보면:

3C2=3!2!(3−2)!=3×2×12×1×1=33C2 = \frac{3!}{2!(3-2)!} = \frac{3 \times 2 \times 1}{2 \times 1 \times 1} = 33C2=2!(3−2)!3!​=2×1×13×2×1​=3

따라서, 3C2=33C2 = 33C2=3은 "3개의 원소 중 2개를 뽑는 방법이 3가지"라는 뜻입니다.

---

2. 공식 C[i]×(C[i]−1)/2\text{C[i]} \times (\text{C[i]} - 1) / 2C[i]×(C[i]−1)/2의 의미

코딩적으로 nC2nC2nC2를 효율적으로 구하기 위해 이 공식을 활용합니다.

• C[i]C[i]C[i]는 현재 그룹에서 원소의 개수를 나타냅니다.
• C[i]×(C[i]−1)/2C[i] \times (C[i] - 1) / 2C[i]×(C[i]−1)/2는 다음과 같은 과정을 포함합니다:

1단계: 가능한 모든 쌍의 경우의 수

C[i]×(C[i]−1)C[i] \times (C[i] - 1)C[i]×(C[i]−1)는 서로 다른 두 원소를 순서를 고려해 뽑는 경우를 계산합니다. 이는 순열을 나타냅니다.

2단계: 순서를 고려하지 않는 조합으로 변환

조합에서는 순서를 고려하지 않으므로, 각 쌍을 2로 나누어 중복을 제거합니다. 따라서:

C[i]×(C[i]−1)2\frac{C[i] \times (C[i] - 1)}{2}2C[i]×(C[i]−1)​

이 조합의 결과를 반환합니다.

---

3. 예제: 3개의 원소 중 2개를 뽑는 경우

예를 들어, C[i]=3C[i] = 3C[i]=3이라고 가정해봅시다:

1. 가능한 쌍의 수:

3×(3−1)=63 \times (3 - 1) = 63×(3−1)=6

이는 두 원소를 순서를 고려하여 뽑는 방법입니다.

1. 순서를 무시하여 조합으로 변환:

62=3\frac{6}{2} = 326​=3

따라서, 3C2=33C2 = 33C2=3임을 증명할 수 있습니다.

---

4. 실제 코드 구현

이를 바탕으로 nC2nC2nC2를 계산하는 코드를 작성하면 다음과 같습니다:

public class CombinationExample {
    public static int combination(int n) {
        if (n < 2) return 0; // 원소가 2개 미만인 경우 조합 불가
        return (n * (n - 1)) / 2;
    }

    public static void main(String[] args) {
        int n = 3; // 예제: 원소 3개
        System.out.println("3C2의 값: " + combination(n)); // 출력: 3
    }
}

 

# 추가질문 

C[i]×(C[i]−1) 이 수식에서 잘 이해가 안가는 부분이 있는데
C[i] 가 현재 그룹에서 원소의 개수를 나타내는거 까지는 그렇다 치는데, (C[i]−1)를 왜 해주는거야? 왜 -1을 하는지 모르겠어

 

좋은 질문이에요!

C[i]×(C[i]−1)C[i] \times (C[i] - 1)C[i]×(C[i]−1)에서 (C[i]−1)(C[i] - 1)(C[i]−1)을 하는 이유는 같은 그룹 내에서 두 원소를 선택할 때, 중복 없이 서로 다른 원소만 선택하기 위해입니다. 이를 단계별로 살펴볼게요.

---

1. 문제 상황: 두 원소를 뽑는 경우

우리가 C[i]C[i]C[i]개의 원소가 있는 그룹에서 서로 다른 두 원소를 선택하려고 한다고 가정해 봅시다.

예: C[i]=3C[i] = 3C[i]=3인 경우

그룹에 3개의 원소가 있다고 가정합시다. 이 원소들을 A,B,CA, B, CA,B,C라고 부를게요. 우리는 이 중에서 두 개를 선택하려고 합니다.

가능한 조합은 다음과 같습니다:

• (A,B)(A, B)(A,B)
• (A,C)(A, C)(A,C)
• (B,C)(B, C)(B,C)

총 3개의 경우가 존재합니다.

---

2. 각 원소가 선택될 때 다른 원소를 선택할 수 있는 개수

각 원소를 선택했을 때, 나머지 다른 원소들과 짝지어야 합니다. 예를 들어:

• AAA를 선택하면, 나머지 선택 가능한 원소는 B,CB, CB,C → 2개
• BBB를 선택하면, 나머지 선택 가능한 원소는 A,CA, CA,C → 2개
• CCC를 선택하면, 나머지 선택 가능한 원소는 A,BA, BA,B → 2개

이렇게 C[i]C[i]C[i]개의 원소 각각이 다른 (C[i]−1)(C[i] - 1)(C[i]−1)개의 원소와 조합될 수 있습니다.

일반화:

• C[i]C[i]C[i]: 선택할 수 있는 원소의 개수
• C[i]−1C[i] - 1C[i]−1: 선택된 원소를 제외한 나머지 원소의 개수

---

3. 중복 포함 시 계산

위 계산을 수식으로 표현하면:

C[i]×(C[i]−1)C[i] \times (C[i] - 1)C[i]×(C[i]−1)

이 값은 각 원소가 나머지 원소들과 짝지어진 경우를 모두 포함합니다. 예를 들어:

• (A,B)(A, B)(A,B)와 (B,A)(B, A)(B,A)는 사실 같은 조합이지만, 이 수식에서는 순서를 고려하기 때문에 중복으로 계산됩니다.

---

4. 중복 제거

조합에서는 순서를 고려하지 않으므로, 중복된 경우를 제거하기 위해 2로 나눕니다:

C[i]×(C[i]−1)2\frac{C[i] \times (C[i] - 1)}{2}2C[i]×(C[i]−1)​

이를 통해 C[i]C[i]C[i]개의 원소 중 서로 다른 두 원소를 조합하는 경우의 수를 정확히 계산할 수 있습니다.

---

5. 결론

• C[i]−1C[i] - 1C[i]−1을 사용하는 이유는 선택한 원소를 제외한 나머지 원소의 개수를 계산하기 위해서입니다.
• C[i]×(C[i]−1)C[i] \times (C[i] - 1)C[i]×(C[i]−1)는 순서를 고려한 모든 경우를 구하는 수식이고, 여기서 2로 나누면 순서를 고려하지 않은 조합이 됩니다.

---

추가 예제: C[i]=4C[i] = 4C[i]=4일 때

그룹에 4개의 원소가 있다고 가정해 봅시다 (A,B,C,DA, B, C, DA,B,C,D):

1. AAA: 나머지 원소 B,C,DB, C, DB,C,D와 조합 가능 → 3개
2. BBB: 나머지 원소 A,C,DA, C, DA,C,D와 조합 가능 → 3개
3. CCC: 나머지 원소 A,B,DA, B, DA,B,D와 조합 가능 → 3개
4. DDD: 나머지 원소 A,B,CA, B, CA,B,C와 조합 가능 → 3개

총 4×3=124 \times 3 = 124×3=12개의 경우가 계산됩니다. 중복을 제거하면:

122=6\frac{12}{2} = 6212​=6

이 결과는 4C2=64C2 = 64C2=6과 동일합니다.

 

---

 

순열조합공식 참고링크 : https://coding-factory.tistory.com/606

[수학] 순열, 조합 공식 총정리

---

 

/* 문제 : N개의수 A₁,A₂...Aｎ이 주어졌을때 연속된 부분의 합이 M으로 나누어떨어지는 구간의 개수 구하기 
 *      즉, Aｉ+..+Aｊ(i<=j)의 합이 M으로 나누어떨어지는 (i,j)쌍의 개수를 구하기
 * 1번째줄 : N, 나눌수 M (1<=N<= 10^6, 2<=M<=10^3)
 * 2번째줄 : N개의 수 A₁,A₂...Aｎ이 주어짐(0<=Aｉ<=10^9)
 * */

//Scanner version ======================
		int N ; //N개의 수
		int M ; //나눌수
		long[] S ; //구간합배열
		long[] C ; //나머지값 배열

		int rs = 0; //구간개수
		
		Scanner sc = new Scanner(System.in);
		
		//초기화
		N = sc.nextInt();
		M = sc.nextInt();
		S = new long[(N)]; //구간합배열 초기화 
		C = new long[(M)]; //나머지배열 초기화
		
		//구간합 구하기 
		S[0] = sc.nextInt();		
		for (int i = 1; i <N; i++) {
			S[i] = S[i-1] + sc.nextInt();;	
		}
		
		//합배열을 M으로 나눈 나머지값
		for (int i = 0; i < S.length; i++) {
			int reminder = (int) (S[i] % M); //나머지값 
			 
			//구간합이 0으로 나누어떨어질때(=원본배열 0부터 i까지의 구간합이 이미 M으로 나누어떨어진 상태)
			if(reminder == 0) {
				rs++; //정답 1증가
			}				
			
			//나머지값이 같은 원소의 값이 같은 2개의 원소를 뽑는 경우의수 
			C[reminder]++;
		}
		
		//구간개수 구하기   
		for (int i = 0; i < M; i++) {
			//나머지인 인덱스 개수에서 2가지를 뽑는 경우의 수
			if(C[i] > 1) {
				rs += C[i]*(C[i]-1)/2;				
			}
		}
		
		System.out.println("정답 : " + rs );