[백준 10986] 나머지 합 구하기 feat 누적합

Status

Published

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 10^6, 2 ≤ M ≤ 10^3)

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

출력

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

www.acmicpc.net

냅다 풀기


예제입력
5 3 // 공백을 기준으로 두개의 값이 들어온다.
			첫번째 값 N은 A배열의 크기, 두번째 값은 나눌 값 M
1 2 3 1 2 // N크기의 배열

모든 부분 구간의 합을 검사하여 그 합이 M으로 나누어 떨이지면 count++ 하는건가?

ex : 배열 A = [1, 2, 3, 4]


N, M = map(int, input().split())
A = list(map(int, input().split()))

count = 0
for i in range(N): // 구간의 출발점
    sum = 0
    for j in range(i, N): // 구간의 도착점
        sum += A[j]
        if sum % M == 0:
            count += 1

print(count)

O(N²)(이중 for문 으로 시간복잡도가 초과된다.)

O(N²) → 최대 1,000,000 × 1,000,000 = 10¹²번 연산 (1조 번 연산….)

말도안된다. 그렇다면 어떻게 풀어야할까?

필요한 수학적 개념

부분합 (구간합)

A[i] + A[i+1] + … + A[j]
어떤 구간의 합을 계산하는 기본 개념

누적합

누적합 S[i]를 계산해 놓으면 i~j 구간의 합을 쉽게 구할 수 있다.
sum(i~j) = S[j] - S[i-1]

나머지 연산

나머지의 성질!

즉 : 나머지가 같으면 두 숫자의 차이는 M으로 나누어 떨어진다!

+++

구간합과 누적합 이해하고 넘어가기!

시간대	소비금액
오전	5000원
점심	12000원
오후	3000원
저녁	15000원

점심 + 오후의 소비 금액을 알고 싶다면 그냥 12000원 + 3000원 = 15000원 더하면 된다.

하지만 계산해야하는게 이처럼 하루 4번의 데이터가 아닌 장사가 아주아주 잘되는 편의점의 데이터라면?

아침 9시부터 밤 9시까지의 720번의 데이터가 있다고 가정하자

그럼 오후 3시부터 오후 6시까지의 매출은 얼마인가?

매번 오후3시 0초 부터 매초, 매분 데이터를 오후 6시까지 더할건가?

이럴때 누적합으로 구간합 구하기 2


A = [5] [8] [3] [7]

누적합 S = [5] [13] [16] [23]

sum(1~3) = S[3] - S[0] = 23 - 5 = 18

이제 위 개념들을 가지고 문제를 풀어보자.

들어가기전에! 나머지 연산의 성질을 떠올려보자.

나머지가 같으면 두 숫자의 차이는 M으로 나누어 떨어진다!

즉 두 누적합의 나머지가 같으면, 그 구간의 합은 M으로 나누어 떨어진다.

예시를 들어 한번 작성해보자.

입력값

5 5 (크기 5, 나누는값 5)

2 3 1 4 2 일때

배열 [2] [3] [1] [4] [2] 이 있다.

배열 A의 연속 구간합 중에서 5로 나누어 떨어지는 구간의 개수를 구하는 과정이다.

먼저 배열의 누적합을 구한 후 나머지를 구해보자.

여기서 “ 두 누적합의 나머지가 같으면 그 사이의 합이 M의 배수로 딱 떨어진다.”

말이 어렵지 이해하면 쉽다. 정리해보면

누적합을 만든다

나머지를 구한다 (mod M)

같은 나머지끼리 연결해서 구간합을 찾는다

나머지가 0인 경우는 단독으로도 정답이다

방법	개수
S[0]~S[4] (나머지 2끼리 연결)	1개
S[1]~S[3] (나머지 0끼리 연결)	1개
S[1] 단독	1개
S[3] 단독	1개

정답 4개

같은 나머지인 두 개를 뽑아 연결하면 그 사이 구간합이 M의 배수이다.

즉 가능한 모든 쌍을 세야한다. 같은 나머지 값이 3개라면

“같은 나머지 값을 갖는 어떤 두쌍을 선택하여 그 두 쌍으로 만든 구간합은 모두 같은 나머지를 갖는다.”

를 생각하여 경우의수를 계산한다.

이항계수의 개념은 다른 글에서 다루겠다.

조합하는 경우의수를 생각 하면 된다. 너무 딥하게 들어가진 않고 슈도코르 작성하여 코드화로 마무리 짓겠다.


입력: N, M
입력: 배열 A (길이 N)

1. 누적합 S를 계산하면서 S[i] % M 을 저장

2. 나머지의 개수를 세기 위한 배열 modCount 초기화 (길이 M)

3. S[0]부터 S[N-1]까지:
    mod = S[i] % M
    modCount[mod] += 1

4. 정답 = 0

5. 나머지가 0인 경우 (mod == 0):
    자기 자신도 정답에 포함 (modCount[0] 개수 만큼)

6. 같은 나머지끼리 2개씩 뽑는 조합 계산:
    for i in 0 ~ M-1:
        if modCount[i] >= 2:
            정답 += (modCount[i] × (modCount[i]-1)) / 2

7. 출력: 정답


N, M = map(int, input().split())
A = list(map(int, input().split()))

modCount = [0] * M
sum = 0

# 누적합의 나머지 구하면서 개수 세기
for i in range(N):
    sum += A[i]
    mod = sum % M
    modCount[mod] += 1

# 나머지가 0인 경우는 자기 자신도 정답에 포함
result = modCount[0]

# 같은 나머지끼리 2개씩 뽑는 조합 계산
for count in modCount:
    if count >= 2:
        result += (count * (count - 1)) // 2

print(result)