백준: 나머지 합 구하기 - python (구간합)

문제 출처 

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

 

문제 풀이 힌트 

-N의 최댓값이 106이라 연산량이 작게 느껴질 수 있다.

그러나 각 숫자에 대해서 모든 구간합을 또 구해야 하기 때문에 1초 안에 연산은 불가능하다 ~ 

 

구간 합 배열을 이용해보자 

• 누적 합 계산: 리스트 A의 누적 합을 계산하여 새로운 리스트 S에 저장합니다.
• 나머지 계산: 누적 합 배열 S의 각 요소를 m으로 나눈 나머지를 계산합니다.
• 나머지 카운트: 나머지 값이 몇 번 나오는지 카운트하는 리스트 C를 만들어 각 나머지를 카운트합니다.
• 나머지 0 처리: 나머지가 0인 경우는 바로 답에 포함시킵니다. (변경딘 합 배열의 원소 값이 0이라는 뜻은 원본 리스트의 0부터 i 구간까지의 구간 합ㅇ이 이미 m으로 나누어 떨어진다는 뜻. ) 
• 쌍의 조합 계산: 같은 나머지를 갖는 요소들 간의 쌍의 수를 조합 공식 nC2를 사용해 계산하고 답에 더합니다. (변경된 합 배열에서 원소 값이 같은 인덱스의 개수, 즉, 나머지 값이 같은 합 배열의 개수를 센다. 변경된 합 배열에서 원소 값이 같은 2개의  원소를 뽑는 모든 경우의 수를 구해서 정답에 더하면 된다. )

 

 

정답 풀이 코드 

import sys

# 표준 입력을 빠르게 읽기 위해 sys.stdin.readline을 사용
input = sys.stdin.readline

# 첫 줄에서 두 정수 n과 m을 입력받음
n, m = map(int, input().split())

# 두 번째 줄에서 정수 리스트 A를 입력받음
A = list(map(int, input().split()))

# 누적 합을 저장할 리스트 S 초기화 (길이 n, 값은 모두 0)
S = [0] * n

# 나머지 카운트를 저장할 리스트 C 초기화 (길이 m, 값은 모두 0)
C = [0] * m

# S의 첫 번째 요소를 A의 첫 번째 요소로 초기화
S[0] = A[0]

# 정답을 저장할 변수 answer 초기화
answer = 0

# 누적 합 배열 S를 계산
for i in range(1, n):
    S[i] = S[i-1] + A[i]  # 이전 누적 합에 현재 A[i]를 더함

# 누적 합 배열의 각 요소에 대해 나머지 연산 수행
for i in range(n):
    remainder = S[i] % m  # m으로 나눈 나머지를 계산
    if remainder == 0:  # 나머지가 0인 경우
        answer += 1  # 해당 경우의 수를 answer에 추가
    C[remainder] += 1  # 나머지의 카운트를 증가

# 나머지 카운트를 이용해 나머지 쌍의 경우의 수를 계산
for i in range(m):
    if C[i] > 1:  # 나머지가 i인 값이 2개 이상 있는 경우
        answer += (C[i] * (C[i] - 1)) // 2  # 조합 공식 nC2를 이용해 경우의 수 추가

# 최종 결과 출력
print(answer)

 

only 풀이 코드 

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
A = list(map(int, input().split()))
S = [0] * n
C = [0] * m
S[0] = A[0]
answer = 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):
    if C[i] > 1:
        answer += (C[i] * (C[i] -1) // 2)

print(answer)