[10986]나머지 합 구하기.py

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

모듈러 산술 연산

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

구간 합

• S[i] - S[j]는 원본 리스트의 j+1 부터 i까지의 구간 합이다.

S[i] % M의 값과 S[j] % M의 값이 같다면 (S[i]-S[j])%M은 0이다.

• 구간 합 배열의 원소를 M으로 나눈 나머지로 업데이트하고
• S[i]와 S[j]가 같은 (i, j)쌍을 찾으면
• 원본 리스트에서 j+1부터 i까지의 구간 합이 M으로 나누어떨어진다.

풀어보기

리스트A, 합 배열 S 생성

리스트 A
[1, 2, 3, 1, 2]
합 배열 S
[1, 3, 6, 7, 9]

합 배열 S의 모든 값을 M(=3)으로 나머지 연산 수행해 값을 업데이트

%M 연산 후 변경된 합 배열 S
[1, 0, 0, 1, 0]

변경된 합 배열에서 원소 값이 0인 개수만 세어 정답에 더함

• 변경된 합 배열의 원소 값이 0인 것은 원본 리스트의 0부터 i까지의 구간 합이 이미 M으로 나누어떨어진다는 뜻

경우의 수 = +3

변경된 합배열에서 원소 값이 같은 인덱스의 개수, 즉 나머지 값이 같은 합 배열의 개수를 센다.

• 변경된 합 배열에서 원소 값이 같은 2개의 원소를 뽑는 모든 경우의 수를 구하여 정답에 더한다.
• 위의 예에선 0이 3개, 1이 2개이므로 ₃C₂, ₂C₂로 경우의 수를 구하여 더한다.
  ₃C₂ = 3 -> 경우의 수 = +3
  ₂C₂ = 1 -> 경우의 수 = +1
  =>총 경우의 수 = 3 + 3 + 1 = 7

import sys
input = sys.stdin.readline

# n: 수열의 개수
# m: 나누어 떨어져야 하는 수
n, m = map(int, input().split())

# A: 원본 수열 저장 리스트
# S: 합 배열
# C: 같은 나머지의 인덱스를 카운트하는 리스트
# answer: 정답 변수
A = list(map(int, input().split()))
S = [0] * n
C = [0] * m
S[0] = A[0]
answer = 0

for i in range(1, n):
    S[i] = S[i-1] + A[i]  #합 배열 저장

for i in range(n):
    remainder = S[i] % m  # 합 배열을 M으로 나눈 나머지 값
    if(remainder == 0):
        answer += 1
    C[remainder] += 1 # 같은 나머지 인덱스 값 증가

for i in range(m):
    if C[i] > 1:  # 같은 나머지 인덱스가 2개 이상이면
        answer += ((C[i] * (C[i] - 1)) // 2)  # 조합(순서 상관 없이 n개 중 r개 뽑는) 계산 후 결과 값에 더해줌
        # C[i]개 중 2개를 뽑는 경우의 수: C[i] * C[i]-1 / 2

print(answer)

/ 연산과 // 연산

• / 연산을 하면 answer 변수가 float 형태가 됨.
• // 연산을 사용하면 정수 몫을 구하기 때문에 정수 형태