[Swift][누적합] 백준 10986번 (나머지 합)

요구능력

누적합, 수학

 

문제풀이

아래 코드에 빗대어 우리가 구하려는 구간의 누적합이 (i + 1)부터 (j)까지라면 preFix[j] - preFix[i]가 구간합이 될것이다.

문제에서 연속된 부분의 구간합이 M으로 나누어 떨어지는 구간의 개수를 출력하라고 했으므로,

우리가 구해야 하는것은 (preFix[j] - preFIx[i]) % m = 0 이다.

 

여기서 모듈러의 연산을 활용해야 하는데, (preFix[j] % m) - (preFix[i] % m) = 0 로 분배하고,

(preFix[j] % m) = (preFix[i] % m) 가 된다.

 

그래서 누적합을 구하면서 count[나머지] += 1을 통해 누적합 % m의 개수를 저장해준다.

개수를 저장해주는 이유는 이 갯수를 통해 조합을 이용하기 위해서이다.

아래 식은 순열로 예를 들어 count[i]가 4라면 4P2를 하고 2로 나눠서 조합 4C2를 구해준것이다.

result += (count[i] * (count[i] - 1)) / 2

 

조합을 갑자기 왜 이용하냐 하면, 같은 나머지가 나온 수끼리는 더한다음 나누면 나머지가 0이 나온다.

예를 들어서 1 % 3 = 1이라면, 4 % 3 = 1 이다.

맨 처음에 도출한 식인 (preFix[j] - preFIx[i]) % m = 0 대로 하면 0이 된다.

 

마지막에 result + count[0]을 해준 이유는 하나의 숫자가 나누어 떨어지는 경우를 카운팅해준것이다.

후기

생각해내는게 어려운문제 모듈러연산을 활용하는 문제는 종종 있는것같다.

자주풀어서 완전히 내것으로 만들자..!

 

코드

import Foundation
let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nm[0]
let m = nm[1]

var arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var preFix = Array(repeating: 0, count: arr.count)
var count = Array(repeating: 0, count: m)

for i in 0..<arr.count{
    if i == 0 {
        preFix[i] = arr[i]
    }else{
        preFix[i] = (arr[i] + preFix[i - 1])
    }
    count[preFix[i] % m] += 1
}

//print(count)
var result = 0
for i in 0..<m{
    result += (count[i] * (count[i] - 1)) / 2
}

print(result + count[0])