[백준]_10986번_나머지 합 구하기 [C++]

• 문제시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

  1 초

  256 MB

  26020

  7518

  5492

  27.385%

문제

수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.

즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)

둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109)

출력

첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.

입력

 

예제 입력 1

5 3
1 2 3 1 2

7

---

분석

N의 최댓값이 10^6이라 연산량이 적게 느껴질 수 있다. 하지만 잠시 생각해 보면 10^6개의 수에 대하여 모든 구간 합을 구해야 하므로 1초 안에 연산하기는 어렵습니다. 여기서도 구간 합 배열을 이용해야 한다.

나머지 합 문제 풀리의 핵심 아이디어

• (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으로 나누어 떨어진다는 것을 알 수 있다.

N(수열의 갯수), M(나누어 떨어져야 하는 수) 
S(합 배열), C(같은 나머지를 가지는 인덱스를 카운트하는 배열)

for(i -> 1 ~ N) {
		S[i] = S[i-1] + A[i] //합 배열 저장
}

for(i -> 0 ~ N) {
		remainder = S[i] % M //합 배열을 M으로 나눈 나머지 값
		**if(remainder == 0) 정답을 1 증가시키미
		c[remainder] 의 값을 1 증가시킴**
}

for(ㅑ -> 0 ~ M) {
		**C[i] (i를 나머지로 가지는 인덱스의 개수)에서 2가지를 뽑는 경우의 수를 정답에 더하기**
		//C[i]개 중에 2개를 뽑는 경우의 수 계산 공식 -> C[i] * (C[i] - 1) / 2
}
결과값(answer)출력

 

---

C++

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);  // 입출력 속도 향상을 위한 코드
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M;
    cin >> N >> M;

    vector<long> S(N, 0);  // 입력 배열을 저장할 벡터
    vector<long> C(M, 0);  // 나머지 값이 같은 인덱스의 갯수를 저장할 벡터
    long answer = 0;  // 정답을 저장할 변수
    cin >> S[0];  // 첫번째 수는 따로 입력받기

    // 입력 배열의 부분합을 계산하는 부분
    for (int i = 1; i < N; i++)
    {
        int temp = 0;
        cin >> temp;
        S[i] = S[i - 1] + temp;  // 이전 값과 더하여 부분합 계산
    }

    // 합 배열의 모든 값에 % 연산을 수행하고 나머지가 같은 인덱스의 갯수를 세는 부분
    for (int i = 0; i < N; i++)
    {
        int remainder = S[i] % M;  // i번째 합의 나머지 계산
        // 0 ~ i까지의 구간 합 이 0일 때 정답에 더하기
        if (remainder == 0) {
            answer++;
        }
        // 나머지가 같은 인덱스의 갯수 세기
        C[remainder]++;
    }

    // 나머지가 같은 인덱스 중 2개를 뽑는 경우의 수를 더하는 부분
    for (int i = 0; i < M; i++)
    {
        if (C[i] > 1) {
            //나머지가 같은 인덱스 중 2개를 뽑는 경우의 수를 더하기 
            answer = answer + (C[i] * (C[i] - 1) / 2);
        }
    }
    cout << answer << "\n";
}

정수 배열에서 나올 수 있는 모든 부분합 중에서 M으로 나누어 떨어지는 부분합의 개수를 구하는 문제를 해결하기 위한 코드입니다.

• 코드의 작동 원리
  1. N, M을 입력받습니다.
  2. N개의 정수를 입력받아서, 입력된 정수들의 누적합을 저장하는 합 배열 S를 만듭니다.
  3. 합 배열 S의 모든 값에 M으로 나눈 나머지를 구합니다.
  4. 나머지가 0인 값들은 답에 더해주고, 나머지가 같은 값들의 개수를 저장하는 배열 C를 만듭니다.
  5. 배열 C에서 나머지가 같은 값들 중에서 2개를 뽑는 경우의 수를 계산하여 답에 더합니다.
  6. 계산된 답을 출력합니다.

이 코드에서 사용된 핵심적인 아이디어는, 합 배열 S의 각 원소들을 M으로 나눈 나머지들 중에서 나머지가 같은 값들을 찾아내어 그 중에서 2개를 뽑는 경우의 수를 계산하는 것입니다. 이를 통해, 모든 부분합 중에서 M으로 나누어 떨어지는 부분합의 개수를 구할 수 있다.