[BAEKJOON] 10986 나머지의 합

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> using namespace std; int main() { int n, m; scanf("%d %d", &n, &m); vector<int>map(1000001); for (int x = 0; x < n; x++) { scanf("%d", &map[x]); map[x] %= m; } vector<long long>cnt(1001,0); int sum = 0; cnt[0] = 1; for (int x = 0; x < n; x++) { sum += map[x]; sum %= m; cnt[sum] += 1; } long long answer = 0; for (int x = 0; x < m; x++) answer += (cnt[x] * (cnt[x] - 1)) / 2; printf("%lld", answer); return 0; }

더해서 나머지가 같은 것들만 모아 놓는다

모아놓은 것 중에 2개를 골라서 빼면 나머지가 0인 합을 찾을 수 있다

그것은 nC2이기 때문에 마지막에 ((n)(n-1))/2 를 계산하는 것이다.

이 문제는 너무 어려웠다..