백준 문제풀이 : (10986) 나머지 합 - c/c++

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

10986번: 나머지 합

 

시간 제한	메모리 제한	난이도	알고리즘 분류
1초	256 MB	Gold 3	수학 / 누적합

 

 

문제

 

 

풀이

누적합 알고리즘을 응용해서 푸는 문제다. 하지만 시간 제한이 1초이므로 단순히 누적합 배열만 가지고 계산하려고 하면 시간 초과를 뱉어낸다. 또한 입력받는 수 A의 범위가 0<=A<=1,000,000,000 이기 때문에, 누적합 생성 및 기타 계산 시 int 형 범위를 초과할 테스트 케이스도 고려해줘야 한다.

 

1차원 배열이기 때문에 누적합 배열을 구하는 것은 어렵지 않다. 누적합이 무엇인 지 간단하게 설명하고 넘어가자면, 0번 째 수 부터 i 번째 수 까지의 합을 저장해놓은 배열을 뜻한다.

예를 들어 n = { 0, 1, 2, 3, 4, 5 } 라면, n의 누적합 배열은 s = { 0, 1, 3, 6, 10, 15 } 가 된다. 이렇게 누적합 배열을 계산해 놓으면 구간 별 합을 한 번의 계산으로 간단하게 알아낼 수 있다. (일반적으로 계산 편의와 가독성을 위해 배열[0]의 값은 0으로 넣어놓고, 배열의 크기를 n+1 로 잡는 편이다.)

 

n[1]~n[3]의 구간합 : s[3]-s[0] 

n[2]~n[4]의 구간합 : s[4]-s[1]

즉, n[ i ] ~ n[ j ] 의 구간합 : s[ j ] - s[ i-1 ]

 

이런 식이다.

 

문제의 목적이 %M으로 나누어 떨어지는 구간의 개수를 구하는 것임에 주목한다. 문제에서 주어진 Test Case를 가지고 일단 손으로 한번 풀어본다.

 

<Test Case>

5 3
1 2 3 1 2

 

n 배열의 사이즈는 5, m=3. 

n = { 1, 2, 3, 1, 2 } 로 주어진다.

 

n의 누적합 배열을 sum 이라고 하겠다. 

sum = { 1, 3, 6, 7, 9 } 이다. 

 

위 누적합 배열의 각 수를 %m 하여 '나머지 배열'이라는 새로운 배열에 저장해준다. 나머지 배열을 rem 이라고 하겠다.

rem = { 1, 0, 0, 1, 0 } 이 된다.

 

그럼 여기서 한 가지 규칙을 발견할 수 있다. 나머지 값들이 같은 수 끼리는 뺄샘 하였을 시 %m의 값이 0이 된다.

위 rem에서는 0번째와 3번째 자리의 값이 1이니, sum[3]-sum[0] = 6, 즉 n[1]~n[3] 의 총합은 6이며, %m 했을 시 0이 된단 뜻이다.

 

이를 통해 누적합 배열에서 %m의 값이 같은 수 끼리는 뺄샘 시 %m=0 의 조건을 만족한다는 사실을 알 수 있다.

그렇다면 누적합 배열에서 나머지가 0인 개수, 나머지가 1인 개수, 나머지가 2인 개수 .... 나머지가 n-1개인 개수를 각각 알아내, 같은 나머지 그룹 끼리 2개씩 선택하는 조합의 개수를 계산하면 %M으로 나누어 떨어지는 구간의 개수를 알 수 있다. 

 

위 풀이는 s[ i ] - s[ j ] (j > 0) 일 경우의 풀이이므로 s[ i ] - s[ j ] (j==0) 인 경우의 수 까지 더해줘야 한다. 해당 경우의 수는 그냥 sum 구간합 요소 중 %m==0 인 경우의 수를 더해주기만 하면 된다.

 

이 풀이의 반복 횟수를 따져보자. 구간합 배열과 나머지 배열을 계산하는 것에 N번 반복이 필요하고, 나머지 그룹 별 계산 횟수는 M-1 번이다. N의 최댓값은 1,000,000 이고, M의 최댓값은 1,000 이다. 

 

O(n) = 1,000,000 이므로 주어진 시간 1초 내에 충분히 계산 가능한 풀이다.

 

 

코드 작성

#include <stdio.h>
#include <vector>
using namespace std;

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    long long count=0;

    vector<long long> sum(1, 0); //계산 편의를 위해 sum[0]=1로 초기화.
    vector<long long> remain(m, 0);
    //누적합 계산과 아래 25번 줄 연산을 고려해 두 배열 모두 넉넉하게 long long으로 잡는다.

    for (int nn=1 ; nn<=n ; nn++) {
        int num;
        scanf("%d", &num);
        sum.push_back(sum[nn-1]+num); //sum[nn] = sum[nn-1] + num
        remain[sum[nn]%m]++; 
        //%m 연산의 결과값을 인덱스 값으로 삼아, 해당 배열 칸에 개수를 저장
    }

    for (int i=0 ; i<m ; i++) {
        if (i==0) count+=remain[i]; //위 '풀이'에서 설명한 s[ i ] - s[ j ] (j==0) 인 경우의 수
        count+=( remain[i]*(remain[i]-1)/2 ); //각 나머지 구간 별 2개 조합 수 계산
    }

    printf("%lld", count);
    return 0;
}

 

 

END.