[BOJ] 백준 10986 나머지 합 (Swift)

문제

https://www.acmicpc.net/problem/10986

10986번: 나머지 합

풀이

누적 합을 응용하는 문제입니다.

하나씩 전부 확인해서 구한다면 $O(n^2)$의 시간복잡도가 들 것입니다.

먼저 누적 합을 구해줍시다.
구한 누적합 배열을 array라고 칭하겠습니다.

그렇다면 (i, j) 구간의 합이 m으로 나누어 떨어지는지 확인하는 과정은
$(array[j] - array[i - 1]) mod m == 0$ 인 경우 겠네요
이 수식은 다음과 같이 표현할 수 있습니다.

$(array[j]\ \ mod\ \ m) - (array[i - 1]\ \ mod \ \ m) == 0$
$(array[j]\ \ mod\ \ m) = (array[i - 1]\ \ mod \ \ m)$

즉, 누적 합 배열의 요소를 m으로 나눈 나머지 값이 같은 경우가 합이 m으로 나누어 떨어진다는 것과 같습니다.

[1, 2, 3, 1, 2]의 누적합 배열은 [1, 3, 6, 7, 9] 입니다.
이를 3으로 나눈 나머지는 [1, 0, 0, 1, 0] 입니다.

이때 나머지가 0인 것들의 갯수를 세어야 합니다.
왜냐하면 처음부터 ~ 0이 나온 인덱스까지의 합이 m으로 나누어 떨어지기 때문입니다.

누적 합 배열의 첫번째 인덱스를 0으로 할당했다면, 0인 것들의 갯수를 세지 않아도 무방합니다.

누적 합 배열의 첫번째 인덱스를 0으로 할당하지 않았다면,
그 이후, 0은 3개 이므로 $_3C_2$, 1이 2개이므로 $_2C_2$ 을 구해 더해줍시다.

$_nC_2 = n * (n - 1) / 2!$ 가 성립하므로 구해줍시다.

정답은 0의 갯수 3 + $_3C_2 = 3$ + $_2C_2 = 1$ = 7이 나옵니다.

저는 나눈 나머지를 Dictionary로 세어주어서 계산하였습니다.

소스코드

후기

아주 약간의 수학식이 들어갔는데, 아이디어를 떠올리는 것이 어려웠던 문제였습니다.
아이디어만 떠올렸다면 쉽게 풀 수 있을 것 같습니다.