[백준/Python] 10986번 나머지

1️⃣문제 설명

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

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

2️⃣입력

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

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

3️⃣출력

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

---

👩🏻‍💻작성한 코드

import sys

input = sys.stdin.readline

n, m = map(int, input().split())	# 숫자 개수, 나누는 수
num = list(map(int, input().split()))	# 숫자 데이터
S = [0] * n		# 누적합
C = [0] * m		# 같은 나머지의 인덱스 info
cnt = 0		# m으로 나누어떨어지는 구간의 개수

for i in range(n):
    S[i] = S[i-1] + num[i]
    remainder = S[i] % m
    if remainder == 0:
        cnt += 1
    C[remainder] += 1

for i in range(m):
    if C[i] > 1:
        cnt += (C[i] * (C[i]-1) // 2)

print(cnt)

💡코드 설명

이 문제를 해결하기 위해서 알아야할 개념은 ' S[ i ] % m의 값과 S[ j ] % m의 값이 같다면 ( S[ i ] - S[ j ] ) % m = 0 ' 이다. 그래서 나머지 값이 같을 때의 정보를 저장하기 위해 list C를 사용하였고, C[index]는 같은 나머지를 갖는 원소의 개수를 가르킨다.

예를 들어 m이 3일 경우, C[2]는 나머지가 2일 때의 값을 나타낸다.

 

첫번째 for문을 보면,  reminder는 누적합을 m으로 나누었을 때의 나머지 값이고 이때, remainder가 0 일 때 cnt의 값을 +1 해준다. remainder가 0이 아닐 경우, C[remainder]의 값에 +1 해준다. 

 

두번째 for문을 보면, C[remainder]의 값이 2 이상이면 ' ( S[ i ] - S[ j ] ) % m = 0 '의 개념을 적용하기 위해 원소 값이 같은 2개의 원소를 뽑는 경우를 조합 공식을 사용해서 구한다. cnt에 구한 값을 더해준다.