일단 난이도가 골드이고 '누적합' 섹션에 있는 문제니까 단순히 두개의 루프를 사용하는 bruteforce 솔루션이 출제자가 의도한 정답이 아니라는 점을 인정하고 시작해야할 것 같습니다.
현재 님 코드의 시간 복잡도는 O(N^2) 이죠? 당연히 시간 초과 납니다. 이걸 O(N)으로 줄이셔야 합니다. 조금 정수론적인 지식이 있으면 수월하게 풀리는데 문제의 예시를 사용해보면
1 2 3 1 2 의 누적합은
1 3 6 7 9 죠. 어떤 구간 [l, r] 에 대하여 이 구간의 합은 다음과 같이 나타낼 수 있습니다 - rangeSum([l, r]) = rangeSum([0, r]) - rangeSum([l0, l-1])
즉, 이 문제는 구간의 합의 차가 m으로 나누어 떨어지는 경우의 수를 모두 찾는것과 같습니다.
위의 예시에서 m=3의 경우 다음과 같이 생각해볼 수 있습니다
1. 구간합을 m으로 나눈 나머지가 0
여기에 해당하는 집합은 3, 6, 9 입니다
2. 나머지가 1
여기에 해당하는 집합은 1과 7 입니다
3. 나머지가 2
여기에 해당하는 수는 없습니다
따라서 두 구간의 합의 차가 0이 되게 하려면 나머지가 0인 케이스에서 2개, 1인 케이스에서 2개, 2인 케이스에서 2개를 뽑는 경우를 더한 값과 같습니다.
하나 주의해야할 점은 나머지가 0인 경우는 두 간이 아니라 하나만 가지고도 성립합니다. 즉, 구간합 9 의 경우 이 구간은 전체 array 가 되는것이죠.
그렇기에 위의 예시는
1. 1 2 3 1 2 의 누적합 배열 구하기
2. 각 아이템을 m으로 나눈 나머지에 따라 카운팅 분류 {0: 3, 1: 2, 2: 0}
=> 나머지가 0인 경우는 하나의 구간을 뽑는 것으로도 성립 하므로 더미 데이터 하나를 추가함 {0: 3+1, 1: 2, 2: 0}
3. 각 경우에서 2개씩 뽑기 (4C2 + 2C2+ 0) => 7

yeonho12345 1년 전
도와주세요 시간초과.....................................................