백준 10689번 나머지합

문제를 해석해보면 부분합을 이용해서 문제를 해결해야한다 먼저 부분합을 구하고 구간의 합이 M으로 나누어 떨어져야한다

처음에 그렇게 생각하고 모든부분의 합을 for문을 통해서 구하고 (1개 일때 2개 일때 3개일때 … 이렇게) 나온 값을 리스트로 만들고 M으로 나누어 떨어지는것 (나머지ㅏ가 0인것)을 구했는데 단연하게도 답은 나왔지만 시간 초과가 된다

 

해결 방법

부분합에서 m으로 나누어 나머지를 구한뒤 나머지가 같은것이 2개 이상인 경우 그중 2개를 뽑아서 그사이의 부분합을 보면 M으로 나누어 떨어지는것을 알 수 있다

예시)

[1,2,3,4,5] 리스트가 있다고 하자 부분합은 [1,3,6,10,15]가 된다 m=3일때 나머지를 정리하면 [1,0,0,1,0]이 되고 나머지 값의 차가 0이면 그 부분합은 M으로 나누어 떨어진다

 

부분합을 구한뒤에 부분합을 M으로 나누어 나머지를 구한다 나머지는 0~M-1까지 생긴다 이 나머지들을 리스트의 인덱스로 사용하고 해당 나머지가 몇번 나왔는지를 저장한다 그뒤 나머지의 개수중 같은것이 2번이상 나온것을 nC2 조합을 통해서 개수를 구한다 2개를 구한다는것은 중간부분의 부분합을 구하는것이고 처음부터 다 더하는 부분합은 포합되지 않기 때문에 이 부분은 따로 계산해야 된다

import sys
#입력
n,m =  map(int,sys.stdin.readline().split())
a =    list(map(int,sys.stdin.readline().split()))
count = 0 #조건을 만족하는 값 개수
sum_a =[] #부분합저장 
remain_sum =[0]*m #나머지 값을 저장한

t=0
# 부분합 구하기
for i in a:
    t+=i
    k = t % m
    sum_a.append(t)
    remain_sum[k] += 1 #나머지 값의 개수 반
    
for j in range(1,3): #부분합에서 뽑는 개수 사실 for문 안써도 됨
    
    if j == 1:# 처음부터 다더하는 부분합
        for k in sum_a:
            if k % m == 0:
                count +=1        
    else:#중간 부분의 합
        for i in range(0,m):
    
            if remain_sum[i]>=2:
                count += remain_sum[i]*(remain_sum[i]-1)//2 #nC2공식

print(count)