(BOJ10986 나머지 합

• tags : (algorithm

  No matching post could be found

• 문제 링크 : https://www.acmicpc.net/problem/10986
• 풀이 링크
  • Python

• 모든 구간을 탐색할 수 없다.
  • 최대 $10^6$개의 값이 나오므로, $O(N^2)$으로 탐색하면 시간 초과가 날 것이다.
• 대신 누적합으로 먼저 접근해본다.
  • 누적합 기준 M으로 나눈 값을 생각하는 것이므로, 누적합을 구하면 조금 빠르게 접근할 수 있을 것이다.
  • 누적합으로 그대로 접근하면 역시 전체 탐색이 필요할것이므로, 시간초과가 날 것이다.
• 누적합을 그대로 사용하지 않고 M으로 나눈 나머지를 저장하면 어떨까?
  • 이 경우라면 전체 탐색을 고민할 수 있지만,
  • 나눈 나머지가 같은 값을 생각하면 조금 따르게 접근할 수 있다.

N, M = MIIS()
seq = [0] + list(MIIS())
mod_counts = [0] * M
mod_counts[0] += 1
for i in range(N):
    seq[i + 1] += seq[i]
    seq[i + 1] %= M
    mod_counts[seq[i + 1]] += 1
ans = sum([comb(x, 2) for x in mod_counts])
print(ans)

• 전체 코드는 길지 않다.
  • 누적합을 구하는 것과 동시에 나머지를 같이 구하여 저장했다.
  • 그리고 각 구간을 구하여야 하므로 가장 앞에 0값을 추가로 두었다.
• 누적합의 나머지가 같은 위치를 기준으로 잘라서 생각하면 결국 다시 나머지가 0이 될 것이다.