[10986] 나머지 합 (백준)

누적합을 이용하여 풀 수 있다.

모든 경우의 순서쌍을 다 탐색하게 되면 O(n^2)의 시간복잡도로 시간초과가 발생한다.

 

하지만 구간의 합은 누적합의 뺄셈이며 M으로 나눈 나머지는 0 에서 M-1까지 존재한다.

이를 토대로 나머지가 같은 경우의 수를 각각 구한다. 이후 조합을 사용해서 나머지가 같은 구간합 두 가지를 뽑는 경우, 그리고 나머지가 0인 경우를 세주면 정답을 구할 수 있다.

import sys
input = sys.stdin.readline

def solution():
    total = 0
    for r in rems:
        factor = r*(r-1)//2
        total += factor
    total += rems[0]
    print(total)

if __name__ == "__main__":
    N,M = map(int, input().strip().split())
    nums = list(map(int, input().strip().split()))
    sums = [0]*N
    sums[0], total = nums[0], nums[0]
    rems = [0]*M
    for i in range(1, N):
        total += nums[i]
        sums[i] = total
    for i in range(len(sums)):
        rems[sums[i]%M] += 1
    solution()

의견 및 피드백은 언제나 환영합니다 :)