109861 [Swift] 백준 10986 : 나머지 합 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 단순히 누적합 알고리즘으로 접근할 경우에 아래와 같이 시작점과 끝점의 모든 경우의 수를 확인해야 하므로 시간 복잡도가 O(n^2) for i in 0...n-1 { for j in i+1...n { count += ( psum[j]-psum[i] ) % 1 == 0 ? 1 : 0 { { 하지만 여기서 누적합 psum[0]...psum[n] 중 나머지.. 2023. 12. 13. 이전 1 다음
