백준 10986번 - 나머지 합
https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 필요한 배경지식 누적 합 : prefix sum 문제 해결 방법 누적합 알고리즘을 이용하여 1번째부터 n번째까지의 수의 합을 S[n]이라고 나타내면 i번째 수부터 j번째까지 수들의 합 S[i,j]를 S[j] - S[i-1]로 나타낼 수 있습니다. 문제 조건에서 S[i,j] % M이 0인 (i,j)쌍을 구해야 하므로 누적합을 이용하여 식으로 표현하면 ..
알고리즘 공부/문제풀이
2021. 5. 25. 21:28
반응형