10986 (1) 썸네일형 리스트형 [BOJ] 백준 10986 나머지 합 (Swift) 문제 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)$의 시간복잡도가 들 것입니다. 먼저 누적 합을 구해줍시다. 구한 누적합 배열을 array라고 칭하겠습니다. 그렇다면 (i, j) 구간의 합이 m으로 나누어 떨어지는지 확인하는 과정은 $(array[j] - array[i - 1]) mod m == 0$ 인 경우 겠.. 이전 1 다음
