ps:problems:cses:1662
목차
Subarray Divisibility
| ps | |
|---|---|
| 링크 | cses.fi/… |
| 출처 | CSES |
| 문제 번호 | 1662 |
| 문제명 | Subarray Divisibility |
| 분류 |
누적합 |
| 시간복잡도 | O(n) |
| 인풋사이즈 | n<2*10^5 |
| 사용한 언어 | PyPy 3.9 |
| 제출기록 | 0.10s |
| 최고기록 | 0.08s |
| 해결날짜 | 2026/05/07 |
풀이
- 누적합 (Prefix sums) 을 이용하는 기본 유형의 문제
- 누적합을 n으로 나눈 나머지들로 누적합 배열을 만든 다음, 같은 값을 갖는 인덱스 쌍의 개수를 세어주면 된다.
- 간단한 문제이긴 하지만 주의할 점이 있는데, 같은 값을 갖는 인덱스들을 셀때, collections.Counter 나 dict등의 해시 기반 자료구조를 사용하면 TLE가 난다. 의도적인지는 모르겠지만, Hash table hack 에 해당하는 데이터 셋이 들어있다.
- 그냥 일반적인 리스트를 이용해서 카운팅하면 아무 문제가 없다.
코드
collection.Counter를 사용해서 TLE가 나는 코드
그냥 list를 이용해서 카운팅
teflib.labs.intset.FrozenIntCounter를 사용
ps/problems/cses/1662.txt · 마지막으로 수정됨: 2026/05/07 08:58 저자 teferi
토론