백준 - 나머지 합 (19973)

let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
let (N, M) = (input[0], input[1])

let numbers = readLine()!.split(separator: " ").map{ Int(String($0))! }
var dp = [numbers[0]]
var dict = [Int: Int]()
var answer = 0

// 첫 번째 수부터의 부분합 저장
for i in 1..<N {
    dp.append(dp[i-1] + numbers[i])
}

// 부분합의 나머지 계산
for (index, sum) in dp.enumerated() {
    dp[index] = sum % M
    if sum % M == 0 {
        answer += 1
    }
    dict[sum % M] = (dict[sum % M] ?? 0) + 1
}

// 나누어 떨어지는 경우의 수 계산 및 출력
for (key, value) in dict {
    answer += value * (value - 1) / 2
}
print(answer)

모듈러 연산의 성질이랑 조합 사용이라는 아이디어를 떠올리는 게 제일 힘든 문제인 것 같다.