알고리즘 강의 | Do it! 알고리즘 코딩테스트 with Python - 나머지 합 구하기

005 나머지 합 구하기 (백준 10986번)

 

10986번: 나머지 합

N x N 구간합 2차원 리스트를 만들어서 풀 수 있을 거라 생각했는데 그럼 시간 내에 해결할 수 없음을 알게됨

 

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

- (A+B) % C = ((A % C) + (B % C)) % C, 다시 말해 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 결과 이 구간 합으 ㅣ나머지 연산을 한 값을 동일

- 구간 합 배열을 이용한 식 S[i] - S[j]는 원본 리스트의 j+1 부터 i까지의 구간 합이다.

ex) 원본 리스트A가 [ 3, 2, 4, 5, 1 ] 이라면 구간 합 S는 [ 3, 5, 9, 14, 15 ]

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

 

1. 리스트 A의 합 배열 S를 생성합니다.

2. 합 배열 S의 모든 값을 M으로 나머지 연산을 수행해 값을 업데이트합니다.

3. 우선 변경된 합 배열에서 원소 값이 0개인 개수만 세어 정답에 더합니다. 변경된 합 배열의 원소 값이 0이라는 뜻은 원본 리스트의 0부터 i까지의 구간 합이 이미 M으로 나누어떨어진다는 뜻이기 때문입니다.

4. 이제 변경된 합 배열에서 원소 값이 같은 인덱스의 개수, 즉 나머지 값이 같은 합 배열의 개수를 셉니다. 변경된 합 배열에서 원소 값이 같은 2개의 원소를 뽑는 모든 경우의 수를 구하여 정답에 더하면 됩니다. 위의 예에서는 0이 3개, 1이 2개이므로 ₃C₂, ₂C ₂로 경유의 수를 구하여 더하면 됩니다.

 

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):
    remainder = S[i] % m 
    if remainder == 0:
        answer += 1
    C[remainder] += 1

for i in range(m):
# C[i](i가 나머지인 인덱스의 개수)에서 2가지를 뽑는 경우의 수를 정답에 더하기
    if C[i] > 1: 
        answer += (C[i]*(C[i]-1) // 2)

print(answer)