두 숫자의 합이 0으로 나누어 떨어지는 경우의 수 구하기

[kyungseop]

1. 임의의 배열을 입력 받음(모두 양수)
2. 임의의 수 K(양수) 입력 받음
3. 입력받은 배열의 원소를 2개씩 짝을 지여 합을 구하고 해당 수를 K 로 나눈다.
4. K 로 나누었을 떄 양수가 되는 경우의 수를 구한다. ( K는 1보다 크거나 같고 100보다 크거나 같다)

예) 임의의 배열 입력 1 3 2 6 1 2 임의의 수 K 입력 3

결과 5

설명:

• (0,2) -> 1+2 = 3
• (0,5) -> 1+2 = 3
• (1,3) -> 3+6 = 9
• (2,4) -> 2+1 = 3
• (4,5) -> 1+2 = 3

[ermaker]

시간복잡도: O(N+K)

// use c++11
#include <vector>
#include <cstdio>

int f(std::vector<int> const& numbers, int const& k)
{
  int kk = (k + 1) / 2;
  int result = 0;
  std::vector<int> remain(k);

  for(auto const& number : numbers)
    ++remain[number % k];

  for(int i = 1; i < kk; ++i)
    result += remain[i] * remain[k - i];

  result += remain[0] * (remain[0] - 1) / 2;
  if(!(k % 2)) result += remain[kk] * (remain[kk] - 1) / 2;

  return result;
}

int main()
{
  int result = f({1, 3, 2, 6, 1, 2}, 3);
  std::printf("%d\n", result);
  return 0;
}