005 나머지 합

첫 번째 코드

 

구간의 합을 계속해서 구해가면서 나머지가 0인 경우에 count에 1을 추가하는 형식으로 진행!

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
number = list(map(int, input().split()))
count = 0
left = []

for i in range(n):
    m_number = number[i] % m
    left.append(m_number)

for i in range(n+1):
    for j in range(i):
        sum_number = sum(left[j:i])
        if sum_number % m == 0:
            count += 1

print(count)

 

시간 초과....

계속해서 인덱싱해서 더하는 과정에 용량이 많이 소요되는 것 같다....

---

두 번째 코드

 

책의 아이디어를 참고하자!

전체 누적합 리스트(S)를 구하자

그리고 m으로 나누어 나머지(sm)를 확인한다!

만약에 누적합의 나머지(sm)의 개수가 2보다 크면 경우의 수 2개를 계산하는 형식으로 생각하여 나머지가 0인 추가 연속된 범위를 더한다!

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
A = list(map(int, input().split()))
S = [0]*n
C = [0]*m
count = 0

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

for i in range(n):
    sm = S[i] % m
    if sm == 0:
        count += 1
    C[sm] += 1

for i in range(m):
    if C[i]>1:
        count += (C[i] * (C[i]-1) // 2)

print(count)

 

<pseudocode>

n 숫자의 개수, m 나눌 수

A 원래의 수

S 합배열

C 같은 나머지 인덱스 세기

 

for  n만큼 반복:

    S에 합 배열 저장

 

for n만큼 반복:

    if S배열의 원소를 m으로 나눈 나머지가 0이면:

        count += 1

    C[나머지] += 1

 

for m만큼 반복:

    if C[i]가 1보다 크면:

        count += C[i] * C[i]-1 / 2

 

근데 여기서 나머지가 존재하면 안되므로 몫을 구하는 //을 사용하도록 한다

 

통과!

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Gold/10986.%E2%80%85%EB%82%98%EB%A8%B8%EC%A7%80%E2%80%85%ED%95%A9

programmers/백준/Gold/10986. 나머지 합 at main · ornni/programmers