Baekjoon 10986. 나머지 합 / Python

10986. 나머지 합

난이도 : 골드 3
소요 시간 : 10분
날짜 : 2025.01.08
언어 : 파이썬
알고리즘 유형 : 누적

설명 보기전에 문제 풀어보러 가기

1. 문제 설명

1. 숫자 배열이 주어진다.
2. 연속된 부분 구간의 합이 m으로 나누어 떨어지는 구간의 개수를 구한다.

2. 해결 방식

1. 나머지의 개념
   • 두 수 A, B가 있다고 할 때, 두 수의 나머지를 a, b라고 하자.
   • A + B의 나머지는 a + b의 나머지와 같고, A - B의 나머지는a - b의 나머지와 같다.
2. 구간 합
   • 구간 합을 따로 배열로 저장하지 않는다.
   • 0번부터 n-1번 배열을 순차적으로 돌아서 그 나머지를 x라고 했을 때, cnt[x] 에 하나씩 더해준다.
3. 결과값
   • 구간의 나머지 합을 구할 때, 나머지가 같은 구간들을 구해주면 된다.
   • 예를 들어, 1 ~ 9가 나머지 5, 4 ~ 9가 나머지 5라면,1 ~ 3은 나머지가 0이 된다.
   • 나머지가 0인 구간들은 예외적으로 자기 자신이 들어갈 수 있기 때문에 처음에 계산을 해주었다.

3. 정답 코드

import sys;input = sys.stdin.readline

n, m = map(int, input().split())
arr = list(map(int, input().split()))

cnt = [0] * m
now = 0
for i in range(n):
    now = (now + arr[i]) % m
    cnt[now] += 1

res = cnt[0]

for i in cnt:
    res += i * (i - 1) // 2

print(res)