작성하신 로직은 O(N^2) 으로 시간 초과 발생성이 매우 높습니다. (line 23 ~ 33)
입력 데이터가 다음과 같다고 할 때,
a b c d e f g ....
구간합 [b ~ c] 이 M의 배수라고 할 때 => (b+c)%M = 0
[a ~ a] 의 구간합은 a % M 이고,
[a ~ b] 의 구간합은 (a+b) % M 이고,
[a ~ c] 의 구간합은 (a+b+c) % M = a % M 입니다.
구간합 [c ~ e] 이 M의 배수라고 할 때 (c+d+e)%M = 0
[a ~ b] 의 구간합은 (a+b) % M 이고,
[a ~ e] 의 구간합은 (a+b+c+d+e) % M = (a+b) % M 입니다.
이를 활용해서 i번째 값에 대해서
sum( 0번째 ~ i번째) % M 과 같은 값이 i-1번째까지 총 몇개인가? 로 바꿀 수 있고
이를 O(N) 으로 구할 수 있습니다.

surrie0813 1년 전
왜 시간초과가 발생하는지 모르겠습니다 ㅠㅠ 해결법좀 알려주세요