시간 복잡도가 제곱에 비례합니다. M으로 나눈 나머지가 같은 누적 합의 구간 [1, i], [1, j], [1, k] (i < j < k)이 있다고 하면 [i + 1, j], [i + 1, k], [j + 1, k]로 총 3개 구간에서 나머지가 0이 됩니다. 이 아이디어를 이용하면 O(N + M)으로 해결할 수 있습니다.
10986번 - 나머지 합
시간 복잡도가 제곱에 비례합니다. M으로 나눈 나머지가 같은 누적 합의 구간 [1, i], [1, j], [1, k] (i < j < k)이 있다고 하면 [i + 1, j], [i + 1, k], [j + 1, k]로 총 3개 구간에서 나머지가 0이 됩니다. 이 아이디어를 이용하면 O(N + M)으로 해결할 수 있습니다.
감사합니다.덕분에 풀었습니다.
댓글을 작성하려면 로그인해야 합니다.
phoenixwing0314 10달 전
누적합 리스트 사용해서 풀었는데...