728x90
1. 문제 설명
수 N개 A1, A2, .... An이 주어진다.
이때 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성해라
즉 A[i] ~ A[j] 의 합이 M으로 나누어 떨어지는 (i,j) 쌍의 개수를 구하는 문제이다.
처음 이분탐색을 이용한 문제로 파악을 하였고 시간초과가 나와 다른 방법을 찾아본 결과 누적합 + 조합에 대한 문제였다.
nC2 공식을 사용하여 문제를 풀 수 있다.
728x90
'백준 C++' 카테고리의 다른 글
| 백준 16928번 뱀과 사다리 게임 C++ (0) | 2025.06.01 |
|---|---|
| 백준 11779번 최소비용 구하기 2 C++ (0) | 2025.05.28 |
| 백준 9465번 스티커 C++ (0) | 2025.05.27 |
| 백준 1753번 최단 경로 C++ (0) | 2025.05.27 |
| 백준 1197번 최소 스패닝 트리 C+ (0) | 2025.05.21 |
