나머지 합 (10986번) - 백준 (BOJ)

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

10986번: 나머지 합

 

 

백준 - 나머지 합 (10986번)

 

난이도 : Gold 3

알고리즘&자료구조 : Prefix Sum (누적합)

 

 

class ResSum():
    def __init__(self):
        self.N, self.M = map(int, input().split())
        self.arr = list(map(int, input().split()))
        self.get_num_of_intervals()
        
    
    def get_num_of_intervals(self):
        memo = [0] * self.M
        acc = 0
        for i in self.arr:
            acc = (acc + i) % self.M
            memo[acc] += 1
        cnt = memo[0] + sum(map(lambda i: i*(i-1)//2, memo))
        self.cnt = cnt
        
    
if __name__ == '__main__':
    answer = ResSum()
    print(answer.cnt)

 

 

누적합을 활용하는 문제이다.

 

---

 

▶ 먼저 주어진 숫자 리스트의 누적합을 구한다.

 

일반적인 누적합과의 차이점은,

각 단계마다 M 으로 나눈 나머지를 기록한다는 점이다.

 

1 2 3 1 2  →  1 0 0 1 0

 

 

▶ 위처럼 누적합을 계산하고 나면, 리스트에는 [0, M-1] 범위의 숫자만 남게 된다.

 

리스트에서 서로 같은 숫자 간에 빼주면,

그 사이의 범위는 M 으로 나누어 떨어지기 때문에

숫자 x 의 개수가 n 개라면, nC2 개 만큼의 M 으로 나눠지는 구간이 있다.

 

이것을 [0, M-1] 사이의 모든 숫자에 대해 진행하면 된다.

 

예외적으로 0은, 0 단독으로도 M 으로 나눠지는 구간이기 때문에

리스트에서 0의 개수를 추가로 더해줘야 한다.

 

 

 

▶ 위와 같이 구현하면, M 으로 나눠지는 구간의 갯수를 셀 수 있다.