누적합 (1) 썸네일형 리스트형 백준 [10986] 나머지 합(Python3) 문제 링크 : https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 지문 해석 연속된 부분 구간의 합을 보고 바로 누적합을 써야 한다는 것을 알았다. 완전 탐색 누적합 배열이 있을 때, 한 누적합을 기준으로, 그 이전 위치의 누적합과 차를 비교해 M의 배수가 되는 쌍을 센다. -> O(N^2)로 시간 초과 완전 탐색 최적화 - 탐색 범위 줄이기 누적합은 계속 커진다는 점을 이용해 두 누적합의 차가 M보.. 이전 1 다음