BOJ 10986 나머지 합

백준님이 BOJ 2015 수들의 합 4 풀이중에 10986번 문제는 nC2 를 이용해서 풀 수 있다고 하셨는데, 그래서 풀려고 봤더니 이미 내가 5달 전에 그렇게 풀어놨다.

그런데, 잘 기억은 안나서 이참에 다시 풀어보고 정리해보려고 한다.

이 문제는 연속된 부분 구간이 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 문제인데, 연속된 부분 구간의 합은, 예를 들어 a[s]에서 a[e]까지의 합은 누적합을 이용하면,
psum[e]-psum[s-1]이 된다.
이 때 psum[e]==aM+x, psum[s-1]=bM+y라고 하면 psum[e]-psum[s-1]을 M으로 나눈 나머지가 0이 되려면 M(a-b)+(x-y) 에서 x-y가 0이 되어야 한다. x, y는 M보다 작고 당연히 x-y도 무조건 M보다 작으므로 M의 배수가 될 수는 없다.  즉, x==y여야 한다.

그러니까 누적합에서 나머지가 같은 것 끼리 짝지으면 그것이 M으로 나누어 떨어지는 구간의 개수가 될 것이다.
그래서 누적합을 구하면서 각 누적합을 M으로 나눠 M의 나머지에 해당하는 개수를 기록해놓고, 각 나머지 개수에 k에 대한 kC2를 다 더하면 된다.

단, 여기서 하나 주의할 점은 누적합 중 나머지가 0인 것들의 처리인데, 나는 나머지가 0인 것들의 개수를 셀 때 psum[0]은 포함시키지 않아서 문제가 되었다.
psum[0]을 포함시켜 kC2를 계산하든지, 포함시키지 않았다면 나머지가 0인 psum-psum[0]도 나머지가 0이기 때문에 마지막에 나머지가 0인 것의 개수를 따로 더 해주면 된다.

일주일 뒤에 다시 풀었는데.. 메모리를 줄이기 위해서 그냥 psum변수 하나로 누적합을 구했다. 왜냐하면 필요한 것은 누적합이 아니라 누적합을 m으로 나눈 각 나머지에 해당하는 누적합의 개수이므로 굳이 배열에 저장해 놓을 필요 없이 누적합을 구하는 즉시 바로 계산하면 된다. 그런데 오늘 계속 runtime error가 나서 각 나머지에 해당하는 개수를 기록하는 cnt배열의 크기를 1000에서(m이 1000이므로 나머지는 0~999) n의 크기만큼 늘리니까 runtime error가 나지 않는 것이었다... 그래서 내가 m값으로 1000 이상의 데이터가 들어오는지 혹은 psum%m값이 0~999 범위를 벗어나는지 확인하려고 일부러 runtime error를 발생시키는 코드를 넣었는데도 전혀 그런 범위를 벗어나는 경우는 없었다.

결국 알아낸 것은... 마지막에 kC2 를 계산할 때 내가 0~m-1까지가 아닌 0~n까지로 했던 실수를 발견했다... 그런 줄도 모르고 여태 엉뚱한데서 문제를 찾고 있었던 것이다...
정신차리자!