[Python] 백준 10986번 : 나머지 합

https://www.acmicpc.net/problem/10986

10986번: 나머지 합

---

💡 문제 풀이

구간합을 빙자한 수학 문제이다.

✔️ 느낀 점

2트하고 시간복잡도를 도저히 개선하지 못할 것 같아서 포기하고 넘어갔다.

💻 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
arr = list(map(int, input().split()))
prefixSum = [[0] * n for _ in range(n)]
cnt = 0

for i in range(n):
    for j in range(n):
        if i > j: continue
        prefixSum[i][j] = arr[j]
        if i < j: prefixSum[i][j] += prefixSum[i][j-1]

        if prefixSum[i][j] % m == 0:
            cnt += 1
        
print(cnt)

import sys
input = sys.stdin.readline

count = 0
n, m = map(int, input().split())
arr = list(map(int, input().split()))
prefixSum = [0] * n

prefixSum[0] = arr[0]
for i in range(1, n):
    prefixSum[i] = prefixSum[i-1] + arr[i]

for i in range(n):
    for j in range(n):
        if i > j: continue
        if i != 0:
            prefixSum[j] -= arr[i-1]
        
        if prefixSum[j] % m == 0:
            count += 1

print(count)

import sys
input = sys.stdin.readline

cnt = 0
n, m = map(int, input().split())
arr = list(map(int, input().split()))
remainder = [0] * m
remainder[0] = 1

total = 0
for i in range(n):
    total += arr[i]
    r = total % m
    remainder[r] += 1

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

print(cnt)