[백준] 10986번 : 나머지 합 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

10986번: 나머지 합

 

1. 문제 설명

2. 풀이과정

N의 최댓값이 106이라 연산량이 작게 느껴질 수 있겠지만 106개의 수에 대하여 모든 구간 합을 구해야 하므로 1초 안에 연산하기는 어렵다.

나머지 합 문제 풀이의 핵심 아이디어는 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 이 구산 합의 나머지 연산을 한 값은 동일해야 한다는 것이다. (A + B) % C = ((A % C) + (B % C)) % C

S[i] % M == S[j] % M → (S[i] - S[j]) % M = 0

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

 

합 배열을 구하고 각 합 배열의 값을 M으로 나누어 해당 결과가 0인 개수만 세어 정답에 더한다.

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

다음으로 합 배열에서 각 원소의 나머지 값이 같은 합 배열의 원소 개수를 센다. (배열 C에 각 나머지별 개수 저장)나머지 값이 같은 2개의 원소를 뽑는 모든 경우의 수를 구해 정답에 더하면 된다.

 

슈도코드

1. N, M 입력받기 (수열의 개수, 나누어 떨어져야 하는 수)
2. A 입력받기 (원본 수열 저장 리스트)
3. S 선언하기 (합 배열)
4. for i → N - 1 : S[i] = S[i - 1] + A[i] (합 배열 저장)
5. C 선언하기 (같은 나머지의 인덱스를 카운트하는 리스트)
6. answer 선언하기 (정답 변수)
7. for i → M - 1
8. r = S[i] % M (합 배열을 M으로 나눈 나머지 값)
9. if (r == 0) : answer += 1
10. C[r] += 1
11. for i → M - 1
12. C[i](i가 나머지인 인덱스의 개수)에서 2가지를 뽑는 경우의 수를 정답에 더하기
13. C[i]개 중 2개를 뽑는 경우의 수 계산 : C[i] * (C[i] - 1) / 2

반응형

3. 소스코드

import sys

N, M = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))

S = [0] * N
for i in range(N):
    S[i] = S[i - 1] + A[i]
    
C = [0] * M
answer = 0
for i in range(N):
    r = S[i] % M
    if (r == 0):
        answer += 1
    C[r] += 1
    
for i in range(M):
    if (C[i] > 1):
        answer += (C[i] * (C[i] - 1) // 2)

print(answer)