문제
https://www.acmicpc.net/problem/10986
10986번: 나머지 합
수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j)
www.acmicpc.net
풀이
import sys
input = sys.stdin.readline
n,m = map(int, input().split())
a = list(map(int, input().split()))
s = [0] * n # 합 배열
c = [0] * m # 같은 나머지의 인덱스를 카운트 하는 리스트
answer = 0
s[0] = a[0]
for i in range(1, n):
s[i] = s[i-1] + a[i] # 합 배열 저장
for i in range(n):
rem = s[i] % m # 합 배열을 m으로 나눈 나머지 값
if rem == 0:
answer += 1
c[rem] += 1
for i in range(m):
if c[i] > 1:
answer += (c[i]*(c[i]-1)//2) # C[i] 개 중 2개를 뽑는 경우의 수 계산
print(answer)
설명
- 구간 합 배열을 이용해야 함
1. (A+B)%C는 ((A%C) + (B%C)) %C 와 동일하다. => 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 이 구간 합의 나머지 연산을 한 값은 동일하다.
2. S[j] % M 의 값과 S[i] %M의 값이 동일하면 (S[j] - S[i]) %M은 0이다.
=> 구간 합 배열의 원소를 M으로 나눈 나머지로 업데이트 하고 S[j] 와 S[i] 가 같은 (i, j) 쌍을 찾으면 원본 리스트에서 i+1 부터 j 까지의 구간 합이 M으로 나누어 떨어진다는 것을 알 수 있다.
'Coding Test > Python' 카테고리의 다른 글
| [백준] 오큰수 (1) | 2023.07.05 |
|---|---|
| [백준] 최솟값 찾기 (0) | 2023.07.03 |
| [백준] 구간 합 구하기 5 (0) | 2023.07.01 |
| [Python] 씨름 선수(그리디) (0) | 2023.06.29 |
| [Python] 회의실 배정(그리디) (0) | 2023.06.28 |