[BAEKJOON] 백준 13900: 순서쌍의 곱의 합 (C#)

문제 링크

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

 

 

문제

N개의 정수 중 서로 다른 위치의 두 수를 뽑는 모든 경우의 두 수의 곱의 합을 구하라.

예를 들어 N = 3이고 주어진 정수가 2, 3, 4일 때, 두 수를 뽑는 모든 경우는 (2, 3), (2, 4), (3, 4)이며 이때 각각의 곱은 6, 8, 12이다. 따라서 총합은 26이다.

 

 

입력

첫 번째 줄에는 입력 받을 정수의 개수 N(2 ≤ N ≤ 100,000)

두 번째 줄에는 N 개의 정수가 주어진다. 이때 입력 받는 정수들의 범위는 0이상 10,000 이하이다.

 

 

출력

모든 경우의 곱의 합을 출력한다.

 

 

 

통과한 답안

namespace _13900
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int[] numbers = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            long totalSum = numbers.Sum();
            long squareSum = 0;
            long answer = 0;

            for (int i = 0; i < N; i++)
            {
                squareSum += numbers[i] * numbers[i];
            }

            answer = (totalSum * totalSum - squareSum) / 2;

            Console.WriteLine(answer);
        }
    }
}

 

 

N개의 수가 주어졌을 때, 서로 다른 위치의 두 수를 뽑는 모든 경우의 수의 곱의 합을 구하는 문제이다.

 

간단하게 생각하면 for문을 2개 사용하여 아래와 같이 코드를 구현할 수 있으나

namespace _13900
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int[] numbers = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            long sum = 0;

            for (int i = 0; i < N; i++)
            {
                for (int j = i + 1; j < N; j++)
                {
                    sum += numbers[i] * numbers[j];
                }
            }

            Console.WriteLine(sum);
        }
    }
}

위와 같이 코드를 구현하면 시간 복잡도가 N^2이 되므로 시간 초과가 발생하게 된다.

 

따라서 이를 개선하기 위해서 수학적 성질을 이용하여 풀이할 수 있다.

 

모든 원소의 합(S) = a[0] + a[1] + a[2] + ... + a[N - 1]

모든 원소의 제곱의 합(Q) = a[0]^2 + a[1]^2 + a[2]^2 + ... + a[N - 1]^2

이 때 S를 제곱하면

S^2 = a[0]^2 + a[1]^2 + a[2]^2 + ... + a[N - 1]^2 + 2(a[0]a[1] +a[0]a[2] + ... + a[N - 2]a[N - 1])

이 된다.

 

따라서 원하는 두 수의 곱의 합을 구하기 위해서 S^2에서 Q를 빼주고 2를 나눠주면 된다.

 

예를 들어 예제 1번처럼 N = 3이고 각각의 원소가 2, 3, 4인 경우

모든 원소의 합 S = 2 + 3 + 4 = 9

모든 원소의 제곱의 합 Q = 4 + 9 + 16 = 29

S의 제곱은 (2 + 3 + 4) * (2 + 3 + 4) = 2^2 + 2 * 3 + 2 * 4 + 3 * 2 +3^2 + 3 * 4 + 4 * 2 + 4 * 3 + 4^2

= 2^2 + 3^2 + 4^2 + 2 * (2 * 3 + 2 * 4 + 3 * 4) = 81

원하는 두 수의 곱은 (81 - 29) / 2 = 26이 된다.

 

이 문제는 원하는 결과를 얻기 위해서 일반적인 방법이 아닌

수학적 성질을 이용하는 것을 다시금 일깨워준 문제로,

코딩을 하는데 있어서도 효율성을 높이기 위해서

다양한 지식을 사용할 수 있어야 됨을 배울 수 있었다.