surrie0813   1년 전

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

srand   1년 전

작성하신 로직은 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) 으로 구할 수 있습니다.

댓글을 작성하려면 로그인해야 합니다.