[Swift 알고리즘] 백준 10986 나머지 합

Gold3

×

누적 합, 수학, 순열과조합 

백준 10986번 나머지 합

능력 밖의 문제였다,, 절대 풀 수 없어

 

1차 시도 : 시간초과

직관적으로 누적 합만 사용해서 간단하게 구현해보면 다음과 같다. 

n 의 범위가 100만 이하이니까 중첩 반복문으로 돌리면 O(n^2)으로 당연히 시간초과 뜰 줄 알았음

let nm = readLine()!.split(separator: " ").compactMap { Int($0) }
let (n, m) = (nm[0], nm[1])
let arr = readLine()!.split(separator: " ").compactMap { Int($0) }

var psum = Array(repeating: 0, count: n+1)
for i in 1...n {
    psum[i] = arr[i-1] + psum[i-1]
}

var result = 0
for i in 1...n {
    for j in i...n {
        if (psum[j] - psum[i-1]) % m == 0 {
            result += 1
        }
    }
}
print(result)

 

근데 여기서 뭘 더 어떻게 해줘야 하는거야?!?!? 

도저히 내 머리로는 해결 불가,,

알고리즘 만으로는 풀 수 없는, 수학적인 머리가 필요한 문제여따,, 

풀이 봐도 이해 안감. 

나머지가 같은 개수들 모아서 뽑기(?) 해주는건 알겠는데 그 구현 방식이 

for i in remainder {

    result += i * (i-1) / 2

} 

해주면 어째서 결과가 7이 나오는 거지? 4가 나오는거 아니야? 내가 멍청이인거야?

 

 

 

---

참고 : https://velog.io/@isohyeon/Java-%EB%B0%B1%EC%A4%80-10986-%EB%82%98%EB%A8%B8%EC%A7%80-%ED%95%A9