[BAEKJOON] 백준 23827: 수열 (Easy) (C#)

문제 링크

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

 

 

문제

모든 원소가 양의 정수이고, 길이가 𝑁인 수열 𝐴1,𝐴2,...,𝐴𝑁이 주어진다. 1≤𝑖<𝑗≤𝑁을 만족하는 모든 정수쌍 (𝑖,𝑗)에 대해 𝐴𝑖×𝐴𝑗의 합을 1000000007로 나눈 나머지를 구하시오.

 

 

입력

첫째 줄에 수열 𝐴의 길이 𝑁이 주어진다.

둘째 줄에 수열 𝐴1,𝐴2,⋯,𝐴𝑁이 공백으로 구분되어 주어진다.

 

 

출력

 1≤𝑖<𝑗≤𝑁을 만족하는 모든 정수쌍 (𝑖,𝑗)에 대해 𝐴𝑖×𝐴𝑗의 합을 1000000007로 나눈 나머지를 출력하여라.

 

 

제한

•  2≤𝑁≤500000
•  1≤𝐴𝑖≤500000 (1≤𝑖≤𝑁)

 

 

 

통과한 답안

namespace _23827
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            string[] inputs = Console.ReadLine().Split(' ');
            int[] arr = new int[N];
            long sum = 0;
            long answer = 0;

            for (int i = 0; i < N; i++)
            {
                arr[i] = int.Parse(inputs[i]);
                sum += arr[i];
                sum %= 1000000007;
            }

            for (int i = 0; i < N; i++)
            {
                sum -= arr[i];
                if (sum < 0)
                {
                    sum += 1000000007;
                }
                answer += arr[i] * sum;
                answer %= 1000000007;
            }

            Console.WriteLine(answer);
        }
    }
}

 

길이가 N인 수열에 대해서 1 <= i < j <= N을 만족하는 두 수 Ai * Aj의 합들을 구하는 문제이다.

기본적으로 생각하면 이중 for문을 이용해서 아래와 같이 구할 수 있는데

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

이렇게 된다면 시간 복잡도가 N^2이 되므로 시간 초과가 발생할 수 있다.

 

따라서 다른 방법으로 합을 구하는 방법을 생각해봐야되는데,

길이가 5인 수열에 대해서 생각해보면

(A1 * A2 + A1 * A3 + A1 * A4 + A1 * A5 +

 A2 * A3 + A2 * A4 + A2 * A5 +

 A3 * A4 + A3 * A5 +

 A4 * A5)

가 된다.

즉, A1 * (A2 + A3 + A4 + A5) + A2 * (A3 + A4 + A5) + A3 * (A4 + A5) + A4 * (A5)

로 정리할 수 있다.

 

따라서 전체 합을 구한 뒤에 곱할 수를 뺀 후에 곱해주면 된다.

A1의 경우에는 전체 합 (A1 + A2 + A3 + A4 + A5)에서 A1을 뺀 후에 곱해주면 되고

A2의 경우에는 전체 합에서 A1이 빠진 (A2 + A3 + A4 + A5)에서 A2를 뺀 후에 곱해주면 된다.

이를 코드로 구현한 것이 정답 코드이다.