[C#] 백준 14929 귀찮아 (SIB)

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

 

간단한 조합문제이다. 문제를 풀이하자면 a와 b는 정수이며 1보다 크고 n이하의 범위를 가진다. 그리고 a는 b보다 항상 작다.

 

모든 가능한 a,b에 대해 xaxb 값을 더한 것을 추출하면 된다.

 

즉, 이중합 개념으로 조합으로 풀면 된다. (C(n, 2))

 

이중 for문 (시간 초과)

using System;

class Program
{
    static void Main()
    {
       int n = int.Parse(Console.ReadLine());

       int[] x = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);

        long result = Calculate(n, x);

        Console.WriteLine(result);
    }

    private static long Calculate(int n, int[] x)
    {
        long sum = 0;

        for(int a = 0; a < n; a++)
        {
            for(int b = a + 1; b < n; b++)
            {
                sum += x[a] * x[b];
            }
        }


        return sum;
    }
}

 

당연히 이중반복을 하여 더해주면 된다고 생각했지만, 시간초과에 걸렸다.

 

 

알아봤더니 (∑x)^2 배열의 합을 제곱한 값 = 배열 각 요소의 제곱한 값의 합 + 2 (현재 식) 으로 풀 수 있으며, 이를 다시 정리하면

 

현재 식 = 배열의 합을 제곱한 값 - 배열 각 요소의 제곱한 값의 합 / 2 로 풀 수 있다.

 

배열의 합을 sum, 배열의 각 요소를 제곱한 값을 sum2라고 하면

(sum * sum - sum2) / 2 이렇게 정리된다는 것이다.

 

 

using System;

class Program
{
    static void Main()
    {
       int n = int.Parse(Console.ReadLine());

       int[] x = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);

        long result = Calculate(n, x);

        Console.WriteLine(result);
    }

    // 배열 계산
    private static long Calculate(int n, int[] x)
    {
        long sum = 0;
        long sum2 = 0;

        for(int i = 0; i < n; i++)
        {
            sum += x[i]; // 배열의 합
            sum2 += (long)x[i] * x[i]; // 배열의 각 요소를 제곱
        }


        return (sum * sum - sum2) / 2;
    }
}