[백준 10986] 나머지 합

누적 합과 나머지 연산을 조합하여 해결할 수 있는 문제입니다.

Key Point

본 문제에서 주목할만한 점은 다음과 같습니다.

• (A + B) % C = ((A % C) + (B % C)) % C
• 누적 합을 모아놓은 리스트를 S라고 할때, S[i] % m 과 S[j] % m 이 같은 두 수를 고르면
  (S[i] - S[j]) % m = 0이 되어 j + 1부터 i까지의 구간 합이 m으로 나눠떨어짐을 알 수 있습니다.

해결방법

Key Point를 잘 살펴보겠습니다.
문제를 해결하기 위한 요점은, ‘요소들의 합이 m으로 나눠떨어지는 구간’ 을 구하는 것입니다.
이때, 누적 합을 모아놓은 리스트를 S라고 하고 잘라낼 기준 인덱스를 각각 i와 j라고 하면,
S[i] % m 과 S[j] % m 이 같은 두 수를 골랐을때
(S[i] - S[j]) % m = 0이 되어 j + 1부터 i까지의 구간 합이 m으로 나눠짐을 알 수 있습니다.

..(생략).. [ j + 1번째 요소부터 i번째 요소까지의 합 = S[i] - S[j] ] ..(생략)..

따라서, 먼저 시간 복잡도를 줄이기 위해 ‘누적 합’ 을 모아놓은 리스트가 하나 필요합니다.
그 후에, 각각의 누적합 요소를 m으로 나눈 나머지의 개수를 파악하기 위한 리스트를 추가로 하나 만듭니다.
만약 어떤 누적합 요소를 m으로 나눈 나머지 자체가 0이라면
맨 처음부터 해당 요소까지를 잘라내면 그 구간 자체가 m으로 나눠떨어진다는 것이므로

• 누적 합을 m으로 나눈 나머지 그 자체가 0인 것의 개수를 먼저 더합니다.
• 누적 합을 m으로 나눈 나머지가 서로 같은 두 수를 고르는 경우를 고려하기 위해
  각각의 누적합 요소를 m으로 나눈 나머지의 개수를 모아놓은 리스트를 순회하여
  개수가 2 이상인 경우에는 조합의 개수를 구하는 공식으로 답에 추가해갑니다.

예를 들어보겠습니다.

1 2 3 1 2

숫자들이 위와 같이 주어졌다고 했을 때
누적 합 리스트는 다음과 같습니다.

1 3 6 7 9

또한, 위의 리스트를 m = 3으로 나눈 값들의 리스트는 다음과 같습니다.

1 0 0 1 0

위의 경우에서 0의 개수인 3을 먼저 답에 추가합니다.
그리고 ‘0’ 3개 중에서 2개를 고르는 경우를 더하고 (₃C₂ = 3)
‘1’ 2개 중에서 2개를 고르는 경우를 더합니다. (₂C₂ = 1)
도합 7이라는 정답을 도출해낼 수 있습니다.

해당 코드는 다음과 같습니다.

문제 : 백준 10986 - 나머지 합