백준 10986번 : 나머지 합

첫 번째 코드 : 시간초과

누적합을 이용했고 이중반복문을 사용했다. 시간초과 판정을 받았다.

 

 

두 번째 코드 : 정답

'

수학적 원리를 이용했다. 예를 들어 1 2 3 1 2 가 들어왔다고 해보자. 누적 합 리스트DP를 구해보면 0 1 3 6 7 9 가 된다. 

원래는 여기서 (DP[i]-DP[j])%M == 0인 모든 i j 쌍을 구하는 것이지만 두 개를 빼서 나눴을 때 나머지가 0 이라는 소리는 그 두 개를 각각 M으로 나눴을 때 나머지가 같다는 의미다!  즉 각각을 나누면 0 1 0 0 1 0이 되고 나머지가 같은 것 들을 각각 쌍을 지어주면 되는 간단한 문제가 된다. 0들을 쌍지어주면 6개, 1들을 쌍지어주면 1개가 나와 정답이 7이 된다. 쌍지어주는 것은 nC2 (조합)을 이용했다.